Некоторые аспекты правильных раскрасок графов

с
Оглавление
1 Введение 4
1.1 Определения............................................ 7
1.1.1 Базовые понятия.................................. 8
1.1.2 Понятия, связанные с раскрасками................. 9
1.2 Результаты диссертации................................ 15
2 Динамические Раскраски и Гиперграфы 17
2.1 Верхние оценки на хроматическое число гиперграфов .... 17
2.2 Доказательство теоремы 2.1............................ 19
3 Теорема Брукса и Динамические Раскраски 23
3.1 (с, р)-невырожденность ............................... 23
3.2 Доказательство теоремы 3.1............................ 27
3.2.1 Доказательство теоремы 3.3...................... 31
3.2.2 Доказательство леммы 3.1........................ 39
4 Алгоритмические Аспекты в Теореме Брукса 58
4.1 Формальная постановка задачи.......................... 59
4.1.1 Условие связности............................... G0
2
У
ОГЛАВЛЕНИЕ З
4.1.2 Основной результат .................................. 61
4.2 Задача списочной сі-раскраски............................... 63
4.2.1 Алгоритм............................................. 65
4.2.2 Реализация процедур ................................. 68
4.2.3 Доказательство корректности алгоритма................ 70
4.2.4 Анализ сложности алгоритма........................... 73
4.3 Конструктивное доказательство теоремы Брукса................. 76
Глава 1
Введение
Теория графов является одним из важнейших и интереснейших разделов математики. Помимо многочисленных приложений в различных областях математики, таких как теория вероятностей, комбинаторика, алгебра и топология, она является краеугольным камнем в современной информатике, как теоретической, так и прикладной. В любом учебнике по алгоритмам едва ли не треть всего материала будет посвящена алгоритмам на графах. Терминология теоретической информатики немыслима без использования понятий теории графов, как-то дерево, вершина, ребро, путь, цикл и более сложных, таких как экспандер.
Правильные раскраски графов на сегодняшний день представляются, вероятно, одной из самых популярных и интенсивно изучаемых тем в теории графов. Как наиболее яркие примеры результатов в данной области стоит отмстить классификацию совершенных графов и проблему раскра-шиваемости плоского графа в четыре цвета. Непосредственно связаны с раскрасками хроматический полином и полином Татта, изучению свойств
4
ГЛАВА 1. ВВЕДЕНИЕ
5
которых посвящено большое количество работ в теории графов. Кроме всего прочего, вопросы, касающиеся алгоритмических аспектов правильных раскрасок предоставляют богатое ноле для исследований. Неслучайно задача нахождения хроматического числа графа пошла в знаменитый список из двадцати одной МР-полной задачи, предложенный в 1972 году Р. Карпом.
Хотя уже проблема раскрашиваемости графа в 3 цвета является ХР-I юл ной задачей, существует несколько положительных результатов, описывающих случаи, где число допустимых цветов близко кД - максимальной степени графа. Пожалуй, самой известной среди них является теорема Брукса [17|, утверждающая, что связный граф, не являющийся нечетным циклом или кликой, можно всегда раскрасить в Д цветов. Однако вопрос становится гораздо труднее: уже для раскраски в Д — 1 цвет. В 1977 году Бородин и Косточка 116] выдвинули гипотезу, что для Д > 9 графы без клик размера Д могут быть раскрашены в (Д — 1) цвет. Гипотеза до сих пор остается открытой, однако, в случае Д > 10й она была положительно решена Ридом |40] при помощи вероятностного метода.
Другой способ усилить теорему Брукса, связанный со списочными раскрасками, был независимо предложен Визингом [3) и Эрдошем с соавторами [22]. Недавно это направление даже приобрело большую популярность, чем правильные раскраски (см., например, [28, 46, 33, 311 и многие другие источники, один из самых последних результатов [29]). В 1994 на конференции по теории графов в Обервольхе Томассеном было отмечено, что помимо теоремы Брукса можно также обобщить для списочных раскрасок классическую теорему Галлан [24], в которой описываются все подграфы
ГЛАВА 1. ВВЕДЕНИЕ
в
/г-раскрасочно-критических графов, индуцированных на вершинах степени к — 1. Удивительно, но как отмстил Косточка в [32], обобщение теоремы Галлаи может быть легко выведено из результатов Бородина [1, 2] и Эрдеша, Рубина и Тейлора [22]. Болес подробно, Эрдеш характеризовал (/-сиисочно раскрашиваемые графы, как графы, содержащие блок, который не является ни кликой, ни нечетным циклом. Б этой характеризации никак не упоминается случай раскраски не ^-списочно раскрашиваемого графа, если помимо самого графа задан набор списков (в этом случае ответ может быть отрицательным). Последнее было сделано Бородиным в малоизвестной работе [1|.
Относительно недавно появился ряд работ, в которых доказывается существование правильных раскрасок с некоторыми дополнительными ограничениями и с количеством используемых цветов близким к максимальной степени графа Д. Самым сильным из таких ограничений является условие {3-рсдкости раскраски, ограничивающие количество соседей одного цвета у каждой вершины (см. [27]). Там же доказывается существование [7о</8Д]-редкой правильной раскраски в (Д + 1) цвет для достаточно большой максимальной степени Д. Большинство же работ [38, 34, 9, 10, 7] связаны с условием динамической раскраски, предложенным Монтгомери [38] и требующим. чтобы каждая вершина степени, по крайней мере, два имела соседей двух различных цветов. В работе [34] доказано похожее на теорему Брукса утверждение о динамическом хроматическом числе (минимальное число цветов, необходимое для существования динамической правильной раскраски): *о(<2) < Д((7) + 1 для любого связного графа С при условии Д(С) > 3. Более того, в [34] доказано, что при Д((7) < 3 имеет место нера-