Хроматические числа слоистых графов

• Автор: Берлов, Сергей Львович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Ярославль
• Количество страниц: 86 с. : ил.

Если б? = (V, Е) — граф, то будем обозначать через:

п{С!) = |У| — число вершин С, а т,(С) = Е — число ребер;

если М с V, то б?(М) — индуцированный подграф б, определяемый множеством М;

с1о(х) (степень вершины графа) — количество ребер, содержащих вершину х Е С;

с2(б?) (степень 1'рафа) — максимальная из степеней вершин;

ш(С) (кликовое число графа) — число вершин в наибольшей клике;

(б?) — хроматическое число С, то есть минимально возможное число цветов но всем правильным раскраскам 67;
Хтаг((1,со) — максимальное возможное хроматическое число графа степени С? С ЮШКОВЫМ числом ш

б — дополнительный граф к графу С = (V, 1?);

Ь(С) индуцированный подграф 67, множество вершин которого совпадает с пересечением всех максимальных по мощности клик графа

Т(0) — индуцированный подграф 67, множество вершин которого совпадает с объединением всех максимальных но мощности клик графа С.
Введение.
Теория графов является одним из важнейших и интереснейших разделов математики. В различных областях математики - алгебре, топологии, информатике и других — возникает потребность описания свойств тех или иных объектов на языке теории графов и использования результатов теории графов, что подчеркивает значимость изучения графов и их свойств.
Одним из важнейших и сложнейших направлений исследований в теории графов является изучение хроматических чисел различных графов. Хроматическим числом графа называется наименьшее натуральное число та такое, что граф допускает правильную окраску в та цветов, но не допускает правильную окраску в меньшее количество цветов. Правильной называется такая окраска вершин графа, при которой смежные вершины имеют различные цвета. Одним из наиболее классических результатов в этой области является теорема Брукса, утверждающая, что хроматическое число графа степени та, максимальная клика которого имеет мощность и, равно те. Это утверждение перестает быть верным, если степень графа увеличить до та + 2. Bruce Reed в 1998 году доказал, что для достаточно больших п степень графа в формулировке теоремы Брукса можно увеличить до п + 1(См. [1SJ).
Также было получено множество результатов, связывающих степень графа и его хроматическое число с размером максимальной клики. В частности, хотелось бы отметить статью [31j, в которой доказано, что существует раскраска графа G степени rt с со(G) < та +
в та цветов, в которой максимальная антиклика монохроматична и результат А. В. Косточки [22] установившего, что если d(G) — u>(G) > min{0(rd{Gy/4),0(r2)}, то y(G) < d(G) - r.
Многие исследования были посвящены обобщению теоремы Брукса для различных классов графов, например в статье [34] теорема обобщена на случай графа, не содержащего данного дерева на та + 2 вершинах: доказано, что в этом случае степень графа тоже может быть увеличена до та + 2 для любого та, при этом размер максимальной клики и хроматическое число тоже будут равны та. Также немало усилий было приложено к поиску алгоритмов нахождения правильной окраски графов, например алгоритм Grotschel, Lovasz и Schrijver для окраски совершенного графа за полиномиальное время или алгоритм Карлоффа [35J окраски

графа степени п без Кп+ - Особое место занимает исследование сильного хроматического числа графа, связанного с его разбиением на равномощные множества, вершины которых затем окрашиваются в различные цвета. Оценки, связывающие такие хроматические числа со степенью графа были получены в |2| и развиты в [3J, по сути эти исследования сводятся к получению оценок на хроматические числа слоистых графов, г. е. графов, разбивающихся на равномощпые клики. В дальнейшем, в статье [6] была получена точная оценка на степень слоистого графа, допускающего правильную окраску в количество цветов, равное размеру максимальной антиклики, но только для случая не более, чем трех слоев.
Еще одним популярным направлением исследований являются исследования графов клик, в частности, графов с условием Хелли на клики (Clique-Helly graphs). Обзор результатов по этой тематике можно найти в [13]. В статье [14] было получено описание некоторого вида графов, которые могут быть графами клик для других графов. Оказалось, что таковыми являются именно те графы, которые обладают свойством Хелли для клик. В дальнейшем этот результат был обобщен в статье [15].

С с А и заканчивающийся ребром цвета 1. Тогда (З1 П С2 будет искомым чередующимся путем. Предположим, утверждение леммы ие выполняется. Рассмотрим тогда самый короткий чередующийся путь Р, соединяющий некоторую полуорбиту (), образованной циклом С с нолуорбитой О2, образованной циклом С2 Пусть этот путь соединяет вершину А € 0 с вершиной В Е 0-2- Ясно, что этот путь начинается и заканчивается ребрами цвета 2. Тогда рассмотрим чередующиеся пути Р начинающийся в С и заканчивающийся в А ребром цвета 1, лежащий целиком в 0 и Р2 начинающийся в Со и заканчивающийся в В ребром цве та 1, лежащий целиком в Ог- Тогда путь .PjU.PU.P2 будет чередующимся путем, соединяющим циклы С и С2, что противоречит утверждению леммы 13.

Замечание 5. Ясно, что чередующийся путь, который рассма тривается в лемме 14, не может проходить через вершины других полуорбит, иначе это противоречило бы тому, что никакие две полуорбиты нельзя соединить чередующимся путем.
Будем проделывать многократно процедуру присоединения чередующегося пути к иолуорбите. В частности, можно присоединять к нолуорбите ребро, оба конца которого смежны с вершинами полуорбиты. Через некоторое время получится ситуация, когда не останется ни одного чередующегося пути, соединяющего какие-то две вершины (возможно, совпадающие) какой-то полуорбиты, все вершины которого, кроме концов, лежат вне полуорбит.
Полученные после этого полуорбиты назовем орбитами.
Заметим, что теперь у каждой из пар вершин, соединенных ребром 1 и лежащих вне орбит найдется хотя бы одна вершина, не смежная с вершинами из орбит.