Семейства графов, которые имеют алгоритмы полиномиального времени для вычисления хроматического числа

Сообщение обновлено 31 августа : ниже оригинального вопроса я добавил резюме текущих ответов. Спасибо за все интересные ответы! Конечно, каждый может продолжать публиковать любые новые результаты.

Для каких семейств графов существует алгоритм полиномиального времени для вычисления хроматического числа ?$\chi(G)$

Задача разрешима за полиномиальное время, когда (двудольные графы). В общем, когда , вычисление хроматического числа является NP-трудным, но есть много семейств графов, где это не так. Например, циклы раскраски и совершенные графы могут быть выполнены за полиномиальное время.$\chi(G) = 2$$\chi(G) \ge 3$

Кроме того, для многих классов графов мы можем просто оценить соответствующий хроматический полином; некоторые примеры в Mathworld .

Я полагаю, что большинство из перечисленного является общеизвестным. Я бы с удовольствием узнал, существуют ли другие (нетривиальные) семейства графов, для которых минимальная раскраска графов разрешима за полиномиальное время.

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

Обновление (31 августа):

Спасибо всем за предоставление интересных ответов. Вот краткое резюме ответов и ссылок.

Идеальные и почти идеальные графики

• Геометрические алгоритмы и комбинаторная оптимизация (1988), глава 9 (Стабильные множества в графах). Мартин Грощел, Ласло Ловаш, Александр Шрайвер.

  Глава 9 книги показывает, как решить проблему раскраски с помощью минимально-взвешенной задачи о покрытии кликой. Поскольку они основаны на методе эллипсоидов, эти алгоритмы могут быть не очень полезны на практике. Кроме того, в главе есть хороший список ссылок для различных классов совершенных графов.

• Комбинаторная оптимизация (2003), том B, раздел VI Александр Шрайвер.

  Эта книга состоит из трех глав, посвященных идеальным графам и их полиномиальной окрашиваемости по времени. Я только взглянул, но основной подход кажется таким же, как в предыдущей книге.

• Характеристика b-совершенных графов (2010). Чин Т. Хоанг, Фредерик Маффрей, Мерием Мечеббек

Графики с ограниченной шириной дерева или шириной клика

• Набор доминирующих краев и раскраски на графиках с фиксированной шириной клика (2001). Даниэль Коблер, Udi Rotics

  Алгоритмы здесь требуют k-выражения (алгебраическая формула для построения графа с ограниченной шириной клика) в качестве параметра. Для некоторых графиков это выражение может быть вычислено за линейное время.

• Ярослав указал на методы подсчета раскрасок в ограниченных графах по ширине дерева. Смотрите его ответ ниже.

Эти два семейства изучают графы, в которых можно добавить или удалить вершин или ребер.$k$

• Параметризованная сложность раскраски вершин (2003). Leizhen Cai.

  Раскраска может быть решена за полиномиальное время при добавлении или удалении ребер (для фиксированных ) в расщепленных графах .$k$$k$

• Параметризованные задачи раскраски на хордовых графах (2006). Даниэль Маркс.

  Для фиксированного хордовые графы, к которым добавлено ребер, могут быть раскрашены за полиномиальное время.$k$$k$

Графики, не содержащие отдельных подграфов

• Определение k-колорибельности графов без P5 за полиномиальное время (2010). Чин Т. Хоанг, Марцин Камински, Вадим Лозин, Джо Савада, Сяо Шу.

• Трехцветные AT-свободные графы за полиномиальное время (2010). Юрай Стахо.

Окраска дерева

• Алгоритмы раскраски четырех деревьев (1999). Дэвид Эппштейн, Маршалл В. Берн, Брэд Хатчингс.

Как вы заметили, все совершенные графы могут быть раскрашены за полиномиальное время, но я думаю, что доказательство включает в себя алгоритмы эллипсоида для линейного программирования (см. Книгу Грёшеля, Ловаша и Шрайвера), а не что-либо прямое и комбинаторное. Существует множество различных классов графов, которые являются подклассами совершенных графов и имеют более простые алгоритмы раскраски; Например, хордовые графики можно жадно раскрасить, используя идеальный порядок исключения.

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

Графики максимальной степени три могут быть раскрашены за полиномиальное время: легко проверить, являются ли они двудольными, и если нет, то либо они требуют только трех цветов, либо они имеют K4 в качестве связанного компонента и требуют четырех цветов (теорема Брукса).

Плоские графы без треугольников могут быть раскрашены за полиномиальное время по той же причине: они не более чем 3-хроматические (теорема Грётша).

b-совершенные графы допускают индуцированные 5-циклы (в отличие от совершенных графов), и было показано, что они имеют алгоритм полиномиального времени для раскраски Хоангом, Маффреем и Мечеббеком, Характеристика b-совершенных графов , arXiv: 1004.5306 , 2010.

(Жаль, что замечательный сборник классов графов в ISGCI охватывает только ширину кликов, независимый набор и доминирование. Он не включает информацию о раскраске.)

Также для графиков ограниченной ширины клика (которая является более общей, чем ширина дерева): Коблер и Ротикс .

$n^{f(k)}$

Кроме того, ширину клика сложно вычислить, но есть алгоритм приближения Oum и Seymour, "pproximating ширина клика и ширина ветви" (с экспоненциальной аппроксимацией).

$k$

Любое семейство графов с ограниченной шириной дерева будет иметь алгоритм полиномиального времени для вычисления хроматического числа. Гамарник сводит проблему подсчета раскрасок к задаче вычисления маргиналов некоторых марковских случайных полей, определенных на одном и том же графе. Результат следует из-за того, что маргиналы MRF на ограниченных графах ширины дерева могут быть вычислены за полиномиальное время с помощью алгоритма дерева соединений .

Обновление 8/26 : Вот пример "# окрасок" <-> уменьшение маргиналов. Требуется начать с правильной раскраски, которая может быть найдена за полиномиальное время для ограниченных графов ширины дерева с max-plus версией алгоритма дерева соединений. Теперь подумайте об этом ... вам не нужно количество раскрасок для хроматического числа, только одна правильная раскраска

$P_5$$C_5$$P_5$

$2P_3$

Есть также результаты Даниэля Маркса, касающиеся сложности проблемы хроматических чисел на графах, которая может быть сделана хордальной с помощью не более чем k удалений вершин; для каждого фиксированного k эта проблема является полиномиальной ( http://dx.doi.org/10.1016/j.tcs.2005.10.008 ).

Алгоритмы раскраски четырех деревьев .
М. Берн, Д. Эппштейн и Б. Хатчингс.
http: // arXiv: cs.CG/9907030 .
Algorithmica 32 (1): 87-94, 2002.

Мы рассматриваем несколько вариантов задачи раскраски квадратов квадродерева, чтобы не было двух одинаковых смежных квадратов. Мы даем простые линейные алгоритмы времени для сбалансированных четырех деревьев с 3 раскрасками со смежностью ребер, несбалансированных четырех деревьев с 4 раскрасками со смежностью ребер и сбалансированных или несбалансированных четырех деревьев с 6 раскрасками со смежностью углов. Количество цветов, используемых в первых двух алгоритмах, является оптимальным; для третьего алгоритма иногда может потребоваться 5 цветов.