Расширение предварительной окраски

В теории графов расширение предварительной раскраски — это проблема расширения раскраски подмножества вершин графа с заданным набором цветов до раскраски всего графа, которая не присваивает один и тот же цвет любым двум соседним вершинам. .

Сложность

Расширение предварительной раскраски имеет обычную задачу раскраски графа как особый случай, в котором первоначально окрашенное подмножество вершин пусто; следовательно, оно NP-полно . Однако он также NP-полен для некоторых других классов графов, на которых обычная задача раскраски графов проще. Например, он NP-полн на ладейных графах , для чего соответствует задаче заполнения частично заполненного латинского поля . ^{[ 1 ]}

Задача может быть решена за полиномиальное время для графов ограниченной ширины дерева , но показатель степени многочлена зависит от ширины дерева. ^{[ 2 ]}^{[ 3 ]} Эту проблему можно решить за линейное время для экземпляров расширения предварительной раскраски, в которых ограничено как количество цветов, так и ширина дерева. ^{[ 2 ]}

Связанные проблемы

Расширение предварительной раскраски можно рассматривать как частный случай раскраски списка — задачи раскраски графа, в котором ни одна вершина не окрашена, но каждой вершине присвоен список доступных цветов. Чтобы преобразовать задачу расширения предварительной раскраски в задачу раскраски списка, назначьте каждой неокрашенной вершине в задаче расширения предварительной раскраски список цветов, еще не используемых ее первоначально окрашенными соседями: а затем удалите цветные вершины из графа.

Головоломки судоку можно смоделировать математически как примеры проблемы расширения предварительной раскраски графов судоку . ^{[ 4 ]}^{[ 5 ]}

Ссылки

^ Колборн, Чарльз Дж. (1984), «Сложность заполнения частичных латинских квадратов», Discrete Applied Mathematics , 8 (1): 25–30, doi : 10.1016/0166-218X(84)90075-1 , MR 0739595 .
^ Перейти обратно: ^а ^б Янсен, Клаус; Шеффлер, Петра (1997), «Обобщенная раскраска древовидных графов», Discrete Applied Mathematics , 75 (2): 135–155, doi : 10.1016/S0166-218X(96)00085-6 , MR 1451958
^ Товарищи, Майкл Р .; Фомин Федор Владимирович; Локштанов Даниил; Розамонд, Фрэнсис ; Саураб, Сакет; Зейдер, Стефан; Томассен, Карстен (2011), «О сложности некоторых красочных задач, параметризованных шириной дерева» (PDF) , Information and Computation , 209 (2): 143–153, doi : 10.1016/j.ic.2010.11.026 , MR 2790022
^ Герцберг, Агнес М .; Мурти, М. Рам (2007), «Квадраты судоку и хроматические многочлены», Уведомления Американского математического общества , 54 (6): 708–717, MR 2327972
^ Розенхаус, Джейсон ; Таалман, Лаура (2011), Серьезное отношение к судоку: математика самой популярной в мире головоломки с карандашами , Oxford University Press, стр. 130

Внешние ссылки

Библиография по расширению предварительной окраски , Даниэль Маркс

[1] Колборн, Чарльз Дж. (1984), «Сложность заполнения частичных латинских квадратов», Discrete Applied Mathematics , 8 (1): 25–30, doi : 10.1016/0166-218X(84)90075-1 , MR 0739595 .

[jansch-2] Перейти обратно: ^а ^б Янсен, Клаус; Шеффлер, Петра (1997), «Обобщенная раскраска древовидных графов», Discrete Applied Mathematics , 75 (2): 135–155, doi : 10.1016/S0166-218X(96)00085-6 , MR 1451958

[3] Товарищи, Майкл Р .; Фомин Федор Владимирович; Локштанов Даниил; Розамонд, Фрэнсис ; Саураб, Сакет; Зейдер, Стефан; Томассен, Карстен (2011), «О сложности некоторых красочных задач, параметризованных шириной дерева» (PDF) , Information and Computation , 209 (2): 143–153, doi : 10.1016/j.ic.2010.11.026 , MR 2790022

[4] Герцберг, Агнес М .; Мурти, М. Рам (2007), «Квадраты судоку и хроматические многочлены», Уведомления Американского математического общества , 54 (6): 708–717, MR 2327972

[5] Розенхаус, Джейсон ; Таалман, Лаура (2011), Серьезное отношение к судоку: математика самой популярной в мире головоломки с карандашами , Oxford University Press, стр. 130

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]