Некоторые аспекты правильных раскрасок графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

0046

На правах рукописи

5056

Гравии Николай Вадимович

НЕКОТОРЫЕ АСПЕКТЫ ПРАВИЛЬНЫХ РАСКРАСОК ГРАФОВ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2010

- 2 ЛЕК 2010

004615056

Работа выполнена в лаборатории математической логики Учреждения Российской академии наук Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН

Научный руководитель: кандидат физико-математических наук,

Карпов Дмитрий Валерьевич Официальные оппоненты: доктор физико-математических наук,

профессор Дольников Владимир Леонидович (Ярославский государственный университет имени П. Г.Демидова ) доктор физико-математических наук, Пономаренко Илья Николаевич (Санкт-Петербургское отделение математического института им. В. А. Стеклова РАН) Ведущая организация: Московский государственный университет

имени М. В. Ломоносова

Защита диссертации состоится " с^е^^^узл, 2010 г. в 1С час. на заседании совета Д 212.232.29 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 191023, Санкт-Петербург, наб. р. Фонтанки, 27, ауд. 311 (помещение ПОМИ РАН).

Адрес диссертационного совета: 198504, Санкт-Петербург, Ст. Петергоф, Университетский пр. д. 28.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан "3 "колкой. 2010 г. Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор , Нежинский В. М.

Общая характеристика работы

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

Правильные раскраски графов на сегодняшний день представляются, вероятно, одной из самых популярных и интенсивно изучаемых тем в теории графов. Как наиболее яркие примеры результатов в данной области стоит отметить классификацию совершенных графов и проблему раскрашиваемости плоского графа в четыре цвета. Непосредственно связаны с раскрасками хроматический полином и полином Татта, изучению свойств которых посвящено большое количество работ в теории графов. Кроме всего прочего, вопросы, касающиеся алгоритмических аспектов правильных раскрасок предоставляют богатое поле для исследований. Неслучайно задача нахождения хроматического числа графа вошла в знаменитый список из двадцати одной КР-полной задачи, предложенный в 1972 году Р. Карпом.

Хотя уже проблема раскрашиваемости графа в 3 цвета является ^-полной задачей, существует несколько положительных результатов, описывающих случаи, где число допустимых цветов близко к Д — максимальной степени графа. Пожалуй, самой известной среди них является теорема Брукса, доказанная в 1941 году и утверждающая, что связный граф, не являющийся нечетным циклом или кликой, можно всегда раскрасить в Д цветов. Однако вопрос становится гораздо труднее: уже

для раскраски в Д — 1 цвет. В 1977 году Бородин и Косточка выдвинули гипотезу, что для Д > 9 графы без клик размера Д могут быть раскрашены в (Д — 1) цвет. Гипотеза до сих пор остается открытой, однако, в случае Д > 1014 она была положительно решена Ридом в 1999 году при помощи вероятностного метода.

Другой способ усилить теорему Брукса, связанный со списочными раскрасками, был независимо предложен в середине 80-ых годов Визингом и Эрдешем. Недавно это направление даже приобрело большую популярность, чем правильные раскраски. Среди прочих работ по списочным раскраскам можно назвать работы таких авторов как Войт, Иенсен, Каварабайяши, Косточка, Краточвил, Мохар, Стейбитц, Томассен, Тофт, Туза и многих других. В 1994 на конференции по теории графов в Обервольхе Томассеном было отмечено, что помимо теоремы Брукса можно также обобщить для списочных раскрасок классическую теорему Галлаи, в которой описываются все подграфы /г-раскрасочно-критических графов индуцированных на вершинах степени к — 1. Удивительно, но как отметил Косточка, обобщение теоремы Галлаи может быть легко выведено из результатов Бородина и Эрдеша, Рубина и Тейлора. Более подробно, Эрдеш характеризовал «/-списочно раскрашиваемые графы, как графы, содержащие блок, который не является ни кликой, ни нечетным циклом. В этой характеризации никак не упоминается случай раскраски не ¿-списочно раскрашиваемого графа, если помимо самого графа задан набор списков (в этом случае ответ может быть отрицательным). Последнее было сделано Бородиным в малоизвестной работе 1977 года.

Относительно недавно появился ряд работ, в которых доказывается существование правильных раскрасок с некоторыми дополнительными ограничениями и с количеством используемых цветов близким к максимальной степени графа Д. Самым сильным из таких ограничений, предложенное Хиндом, Моллоем и Ридом, является условие /3-редкости раскраски, ограничивающие количество соседей одного цвета у каждой вершины. Ими же было показано существование |7од8Д]-

рсдкой правильной раскраски в (Д + 1) цвет для достаточно большой максимальной стсшсни Д. Большинство же работ связаны с условием динамической раскраски, предложенным Монтгомери и требующим, чтобы каждая вершина степени, по крайней мере, два имела соседей двух различных цветов. Было доказано (Лай, Монтгомери и Пун 2003) похожее на теорему Брукса утверждение о динамическом хроматическом числе (минимальное число цветов, необходимое для существования динамической правильной раскраски): Хг(С) < Д(С?) + 1 для любого связного графа С? при условии Д((7) > 3. Более того, ими же было доказано, что при Д((7) < 3 имеет место неравенство Хг(С) < 4, за исключением случая, когда граф С? — это цикл из пяти вершин. Эти результаты были существенно усилены Карповым: в 2007 было доказано существование правильной динамической Д-раскраски, кроме серии графов-исключений, для Д > 254 и потом в 2009 при помощи гораздо более сложных методов оценка на максимальную степень была улучшена до Д > 8.

Цели работы.

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

2. Обобщить теорему Брукса с дополнительным ограничением динамичности раскраски.

3. Исследовать свойство динамической раскраски без требования правильности, получить верхние оценки на количество цветов достаточное для существования такой раскраски.

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

Общая методика работы. В работе используются только

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

Основные результаты.

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

2. Разработано новое понятие (с,р)-невырожденной раскраски, обобщающее понятие динамической раскраски. Доказана усиленная теорема Брукса с дополнительным требованием (с,р)-невырожденности.

3. Придуманы линейные по времени алгоритмы

(a) для нахождения правильной раскраски для любого списочного ¿-набора,

(b) для дополнения имеющейся правильной Д-раскраски.

4. Получено новое конструктивное доказательство теоремы Брукса.

Научная новизна. Все результаты диссертации — новые. Доказанная теорема Брукса с дополнительным требованием (с,р)-невырожденности вкупе с аналогом теоремы Брукса для динамических раскрасок (Карпов 2007), использующей эту теорему, отвечает на несколько открытых вопросов поставленных ранее в западной литературе

и приподнимает требование к дальнейшим исследованиям и области динамических раскрасок. Устанавливается связь между динамическими раскрасками и правильными раскрасками гиперграфов и доказывается нетривиальная, хотя и несложная, верхняя оценка на количество цветов в динамической раскраске. Получен оптимальный по времени алгоритм для нетривиальной задачи списочной (/-раскраски, обобщающий лучший известный ранее алгоритм списочной Д-раскраски.

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

Апробация работы. Основные результаты обсуждались на следующих конференциях и семинарах:

• Международный научный семинар Дискретная математика и се приложения, Россия, 2007;

• Международная студенческая школа Estonian Winter School in Computer Science (EWSCS 2009), Эстония, 2009;

• Международная конференция The Fifth Workshop on Internet and Networks Economics (WINE 2009), Италия, 2009;

• Международный семинар Oberwolfach Seminar: New Trends in Algorithms for Real Algebraic Geometry, Германия, 2009;

• Международный симпозиум Fifth International Computer Science Symposium in Russia (CSR 2010), Россия, 2010;

Результаты, лежащие в основе диссертации, также были доложены в Университете Билсфельда (Bielefeld University), в Университете Сингапура

(Nanyaiig Technological University), в исследовательском центре компании Майкрософт в Азии (Microsoft Research in Asia), а также на семинарах ПОМИ РАН.

Публикации. Основные результаты диссертации опубликованы в трех работах [1, 2, 3]. Работа [1] опубликована в издании, входящем в список рекомендованных Высшей аттестационной комиссией на момент публикации. В работе [2| диссертанту принадлежит основная идея доказательства и часть технических выкладок. Карповым Д. В. придумана формулировка теоремы и сделана остальная часть технических выкладок.

Структура и объем диссертации. Диссертация объемом 84 страницы состоит из введения и трех основных глав, разбитых на разделы и подразделы. Список цитируемой литературы состоит из сорока семи наименований.

Содержание работы

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

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

Теорема 1. Пусть "Н — гиперграф с максимальной степенью вершины А, каждое гиперребро которого содержит не менее, чем S вершин. Тогда вершины 7i можно правильно раскрасить в + 1] цветов.

Теорема 2. Граф G допускает динамическую раскраску вершин в t^gt + ч Цветов.

Третья глава посвящена обобщению теоремы Брукса, которая говорит нам, что х(^) ^ Д(^) для любого графа й с Д((3) > 2 без полных подграфов на Л + 1 вершине. Обобщение заключается в том, что дополнительно накладывается требование (с,р)-невырожденности на раскраску графа.

Определение. Пусть даны натуральные числа с > 2 и р > с. Раскраска графа (7 называется (с, р)-невырожденной, если для любой вершины б степени хотя бы р среди ее соседей найдутся вершины хотя бы с различных цветов.

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

Теорема 3. Пусть дано число И > 3 и граф О без клик па Б + 1 вершине с Д(в) < Б. Тогда для любого с > 2 существует правильная (с, р)—невырожденная раскраска вершин графа С в Б цветов, где

р= (с3 + 8с2 + 19с + 6)(с+ 1).

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

Теорема 4. Пусть дан граф С без клик размера О + I с максимальной

с+1

степенью не большей, чем Б. И пусть кроме того Б = а*, где а^ > 2. Тогда в множестве Н раскрасок графа б в с + 1 цвет найдется такая раскраска что:

с+1

V = штФ(^), где Ф = „ > а & " это количество ребер графа соединяющих две вершины г-ого цвета,

2) для любого г раскраска £ не содержит клик размера оц +1 на вершинах г-ого цвета.

3) Дс(У1) < а1, где это множество всех вершин 1-ого цвета в

Кроме того в первом подразделе после применения теоремы 4 теорема 3 сводится к следующей лемме, доказательству которой посвящен весь второй подраздел.

Лемма 1. Пусть дано два непустых множества вершин А и В и некоторый связный граф Н = (А U В,Е), обозначим через Q индуцированный подграф Н(В). Определим dA(v), где v € В, как количество ребер ведущих из вершины v в множество А. Пусть граф Н обладает следующими свойствами:

1) никакие две вершины множества А не соединены ребром;

2) степень каждой вершины из А в графе Н по крайней мере q3 + 2 q2 -q- 8, где q > 4;

3) для любой вершины v Е В выполняется неравенство:

de{v)

где d > q3 + 2q2 - q - 8.

ч»

< d,

Тогда можно раскрасить граф Q правильным образом в d цветов так, чтобы для любой вершины v 6 А среди ее соседей в В были вершины по крайней мере q различных цветов.

В четвертой главе рассматриваются алгоритмические аспекты правильных списочных раскрасок.

Списочным набором является функция С, ставящая в соответствие каждой вершине v е V{G) некоторое множество C(v) натуральных чисел, которые зовутся допустимыми цветами вершины v. Тогда С-раскраской G будет называться такая правильная раскраска с графа G, что каждой вершине v соответствует цвет с(v) G £(v). В случае, если |£(v)| > к для любой вершины v £ V{G), мы будем говорить, что £ является к-набором, если же |£(г>)| > deg(v) для каждой вершины v £ V(G), мы будем говорить, что £ является d-набором. Если граф имеет правильную раскраску с произвольным допустимым к или d-набором, то

-ll-

oro называют соответственно списочно ^-раскрашиваемым или списочно (■¿-раскрашиваемым. Нетрудно видеть, что обычная ¿-раскраска графа соответствует списочному ¿-набору C(v) = {1,..., /.}.

Частичной С-раскраской подмножества вершин S графа G называется £-раскраска индуцированного подграфа G(S). £-раскраска С графа G называется расширением, частичной раскраски С на множестве вершин S, если C(v) — C'(v) для всех v £ S.

Основная часть четвертой главы посвящена описанию и обоснованию алгоритма для нахождения d-сшсочиых раскрасок, время работы которого линейно от размера входа. Из этого алгоритма тривиальным образом можно получить линейный по времени алгоритм для задачи дополнения частичной раскраски.

Алгоритм для нахождения d-списочной раскраски принимает в качестве входных данных граф G = (V, Е) и набор списков £, где C(v) > degc{v) для любой вершины v 6 V. Причем, рассматривается наиболее сжатое задание графа, где вершины представлены целыми числами от 1 до N — а ребра E(G) заданы как список пар. Дополнительно на входные данные накладывается следующее слабое условие, которое уже использовалось ранее в литературе для похожих задач.

Определение. Пусть максимальное значение цветов для С не больше чем c\E(G)\, для некоторой константы с. Тогда мы говорим, что С, удовлетворяет условию плотности цветов.

Задача алгоритма заключается в нахождении правильной С-раскраски G или сообщении, что таковой не существует.

Определение. Назовем блок висячим, если он содержит не более одной точки сочленения, т.е. соответствует висячей вершине в дереве блоков и точек сочленения Т.

Определение. Назовем упорядоченную пару смежных вершин (u,v) различимыми цветом i, если i € С{и) \ C(v).

В основном алгоритме используются следующие вспомогательные процедуры:

1. Рекурсивное удаление вершин. Находит искомую «(-раскраску связного графа б, если С имеет вершину V с |£(г>)| > йеда{у).

2. Нахоэ/сдение блоков в в. Находит представление каждого блока в виде множества его вершин.

3. Поиск цвета, различающего пару (и,у). За один проход по списку и либо находит различающий цвет, либо сообщает о его отсутствие. Требует от нас ввести один бинарный массив С размера с\Е(С)\, который мы будем использовать многократно при каждом применение процедуры.

4. А-раскраска связного графа. Для связного графа Н, который не является ни кликой, ни нечетным циклом, процедура находит правильную раскраску в Д(Я) цветов.

Сам алгоритм описывается следующим образом.

• ШАГ 1. Пусть найдется вершинам £ К с |£(г;)| > (1сда{у). Процедура рекурсивного удаления вершин выдаст нам искомую раскраску и в этом случае мы закончим выполнение алгоритма.

• ШАГ 2. А) Находим все блоки в С и строим дерево блоков и точек сочленения Т.

1. Находим блоки б используя процедуру поиска блоков.

2. Для каждой вершины у графа находим список блоков, содержащих у.

3. Строим двудольный граф Щ, где одна часть состоит из блоков, а другая часть состоит из всех точек сочленения с множеством ребер Е{Н0) = {{у, В) \ у £ В}.

4. Строим дерево блоков и точек сочленения Т в порядке обхода поиска в ширину, т.е. применяя поиск в ширину находим соответствующий порядок В на блоках и точках сочленения, в зависимости от момента начала их обработки в поиске.

В) Берем последний блок В в порядке В и единственную точку сочленения в этом блоке г>0. В следующих шагах мы пытаемся уменьшить £?, удалив вершины В \ {?.'()}, пли найти желаемую раскраску.

ШАГ 3. Пытаемся найти в В пару различимых некоторым цветом вершин (и, у) таких, что и не является точкой сочленения, т.е. и ф

1. Если в В имеется пара вершин (и,г»), различимых цветом с, тогда мы красим и в цвет с и удаляем се из в. В оставшемся графе |£(и)| > <1ед(у), кроме того С = (7 \ {и} связен. Находим раскраску С с помощью процедуры рекурсивного удаления вершин и завершаем работу.

2. Иначе мы переходим к следующему шагу.

ШАГ 4■ Проверяем, является ли блок В кликой или нечетным циклом. Это можно легко проверить, предварительно посчитав степени всех вершин в О.

1. Если В является кликой или нечетным циклом, то мы уменьшаем С", удаляя В \ {г>о}. Из за того, что в ШАГЕ 3 Уо и любая вершина v блока В, смежная с 1>о, не различимы никаким цветом, мы имеем С(уо) Э £(у). Удалим из списка £(уо) список С(у). Затем вернемся к ШАГУ 2 В) и применим его к идущему до В в порядке В блоку. В этом месте алгоритма мы пользуемся свойством порядка В, чтобы эффективно уменьшить С(у0).

2. Другие варианты для В. В этом случае мы обязательно получим желаемую раскраску и завершим работу.

— Раскрасим G(V \ V(B)), применив процедуру рекурсивного удаления вершин к G(V \ В).

— Удалим из C(vq) все цвета, в которые покрашены соседи wu.

— Проверим, одинаковые ли списки допустимых цветов у Vq и любой смежной с ней вершиной и из В.

— Если эти списки разные, тогда пара (зд, и) для оставшихся не покрашенных вершин будет различима некоторым цветом. Дополпим раскраску всего графа аналогично ШАГУ 3.1 и завершим работу.

— В противном случае, применим процедуру А-раскраски к В.

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

Публикации автора по теме диссертации

Статьи в журналах, рекомендованных ВАК:

[1] Гравии Н. В. Невырожденные раскраски в теореме Брукса // Дискретная математика. 2009. Том 21, N 4. С. 10С-128.

Другие публикации:

[2] Гравии Н. В., Карпов Д. В. Заметка о правильных раскрасках гиперграфов // Препринты ПОМИ РАН. 2010. N 7. С. 8

[3] GravinN. Time optimal d-list colouring of a graph // Proceedings of the 5th International Computer Science Symposium in Russia, Vol. 6072 of Lecture Notes in Computer Science. 2010. P. 156-168.

Подписано в печать 13.10.2010. Формат 60x90/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1 Тираж 100 экз. Заказ 452

Отпечатано в типографии ООО «Адмирал»

199048, Санкт-Петербург, В. О., 6-я линия, д. 59 корп. 1, оф. 40Н

1 Введение

1.1 Определения.

1.1.1 Базовые понятия.

1.1.2 Понятия, связанные с раскрасками.

1.2 Результаты диссертации.

2 Динамические Раскраски и Гиперграфы

2.1 Верхние оценки на хроматическое число гиперграфов

2.2 Доказательство теоремы 2.1.

3 Теорема Брукса и Динамические Раскраски

3.1 (с, р)-невырожденность

3.2 Доказательство теоремы 3.1.

3.2.1 Доказательство теоремы 3.3.

3.2.2 Доказательство леммы 3.1.

4 Алгоритмические Аспекты в Теореме Брукса

4.1 Формальная постановка задачи.

4.1.1 Условие связности.

4.1.2 Основной результат

4.2 Задача списочной ¿-раскраски.

4.2.1 Алгоритм.

4.2.2 Реализация процедур

4.2.3 Доказательство корректности алгоритма.

4.2.4 Анализ сложности алгоритма.

4.3 Конструктивное доказательство теоремы Брукса.

Глава

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

Правильные раскраски графов на сегодняшний день представляются, вероятно, одной из самых популярных и интенсивно изучаемых тем в теории графов. Как наиболее яркие примеры результатов в данной области стоит отметить классификацию совершенных графов и проблему раскра-шиваемости плоского графа в четыре цвета. Непосредственно связаны с раскрасками хроматический полином и полином Татта, изучению свойств которых посвящено большое количество работ в теории графов. Кроме всего прочего, вопросы, касающиеся алгоритмических аспектов правильных раскрасок предоставляют богатое поле для исследований. Неслучайно задача нахождения хроматического числа графа вошла в знаменитый список из двадцати одной КР-полной задачи, предложенный в 1972 году Р. Карпом.

Хотя уже проблема раскрашиваемости графа в 3 цвета является МР-полной задачей, существует несколько положительных результатов, описывающих случаи, где число допустимых цветов близко к А — максимальной степени графа. Пожалуй, самой известной среди них является теорема Брукса [17], утверждающая, что связный граф, не являющийся нечетным циклом или кликой, можно всегда раскрасить в А цветов. Однако вопрос становится гораздо труднее: уже для раскраски в А — 1 цвет. В 1977 году Бородин и Косточка [16] выдвинули гипотезу, что для А > 9 графы без клик размера А могут быть раскрашены в (А — 1) цвет. Гипотеза до сих пор остается открытой, однако, в случае А > 1014 она была положительно решена Ридом [40] при помощи вероятностного метода.

Другой способ усилить теорему Брукса, связанный со списочными раскрасками, был независимо предложен Визингом [3] и Эрдешем с соавторами [22]. Недавно это направление даже приобрело большую популярность, чем правильные раскраски (см., например, [28, 46, 33, 31] и многие другие источники, один из самых последних результатов [29]). В 1994 на конференции по теории графов в Обервольхе Томассеном было отмечено, что помимо теоремы Брукса можно также обобщить для списочных раскрасок классическую теорему Галлаи [24], в которой описываются все подграфы

-раскрасочно-критических графов, индуцированных на вершинах степени к — 1. Удивительно, но как отметил Косточка в [32], обобщение теоремы Галлаи может быть легко выведено из результатов Бородина [1, 2] и Эрдеша, Рубина и Тейлора [22]. Более подробно, Эрдеш характеризовал б^-списочно раскрашиваемые графы, как графы, содержащие блок, который не является ни кликой, ни нечетным циклом. В этой характеризации никак не упоминается случай раскраски не ¿/-списочно раскрашиваемого графа, если помимо самого графа задан набор списков (в этом случае ответ может быть отрицательным). Последнее было сделано Бородиным в малоизвестной работе [1].

Относительно недавно появился ряд работ, в которых доказывается существование правильных раскрасок с некоторыми дополнительными ограничениями и с количеством используемых цветов близким к максимальной степени графа А. Самым сильным из таких ограничений является условие ¡3-редкости раскраски, ограничивающие количество соседей одного цвета у каждой вершины (см. [27]). Там же доказывается существование \1од&Д~|-редкой правильной раскраски в (А + 1) цвет для достаточно большой максимальной степени А. Большинство же работ [38, 34, 9, 10, 7] связаны с условием динамической раскраски, предложенным Монтгомери [38] и требующим, чтобы каждая вершина степени, по крайней мере, два имела соседей двух различных цветов. В работе [34] доказано похожее на теорему Брукса утверждение о динамическом хроматическом числе (минимальное число цветов, необходимое для существования динамической правильной раскраски): < А (С?) + 1 для любого связного графа (У при условии

А(С) > 3. Более того, в [34] доказано, что при А (С?) < 3 имеет место неравенство Х2(@) ^ 4, за исключением случая, когда граф С — это цикл из пяти вершин. В работе [7] результат существенно усиливается: доказывается существование правильной динамической Д-раскраски, кроме серии графов-исключений, для Д > 8. В работе [4], которая составляет большую часть настоящей диссертации (подробнее см. главу 3), определяется понятие (с,р)-невырожденных раскрасок, обобщающее динамические раскраски, и доказывается теорема Брукса с этим дополнительным условием. В работе [6] выводится из общих результатов [4] аналогичный работе [7] результат, только для Д > 254.

1.1 Определения

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

В дальнейшем нам понадобятся несколько стандартных определений, которые мы приводим ниже.

1.1.1 Б азовые понятия

Определение. Пусть 5 С V(С). Индуцированным подграфом графа С называется граф на множеством вершин 5 и содержащий те и только те ребра С, оба конца которых лежат в 5.

Пусть С — произвольный граф. Для V/ С ^(С) через £ — И^ мы будем обозначать граф, получающийся при удалении всех вершин множества ТУ и всех выходящих из них ребер. Для Е С Е(С) через С — Е мы будем обозначать граф, который получается при удалении из 6? всех ребер множества ^ (то есть, С - Е = Я(<3) \ Р)).

Через с1едо{и) или с!ед(и) мы будем обозначать степень вершины и в С, т.е. число инцидентных с и ребер. Следуя книге [15] через £((?) и Д(С) мы будем обозначать минимальную и максимальную степени графа (7. Окрестностью вершины у € в графе С? называется множество

Л^с?^) = {и € У{С) : иу £ Вершины из Л^(г>) называются соседями V.

Аналогичные обозначения (у{Н), Е(Н), с£н(г>), 5{Н) и А(Н)) мы будем приляенять для гиперграфа 7~С.

Определение. Обозначим через |(?| размер графа С, определяемый как количество ребер плюс количество вершин в С (то есть, \С\ = |У"(бг)| + \Е(0)\).

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

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

Замечание 1.1. Все вышеописанные определения обобщаются для мульти-графов, где разрешены петли и кратные ребра.

Раскраской графа С называется отображение с : У(С) —> N. Раскраска с называется /¿-раскраской, если всего было использовано не более к цветов, т.е. 1т,(с) С [1 ,к]. Раскраска с называется правильной, если с(у) ф с(и) для любого ии е Е(С).

Пусть с - раскраска (? в к цветов, а множество V' С У (С). Тогда через с(у') мы будем обозначать ограничение отображения с на множество V т.е. раскраску графа 0(У) в к цветов.

Хроматическим числомх((?) называется минимальное количество цветов, которого достаточно для правильной раскраски графа С?.

1. О. В. Бородин. Критерий хроматичности степенного предписания // Труды 1. Всесоюзной конф. по теорет. кибернетике, Новосибирск, 1977, 127-128.

2. О. В. Бородин. Задачи раскраски и покрытия вершин графов индуцированными подграфами // дис. на соиск. учен. степ. канд. физ.-мат: наук, Новосибирский Государственный Университет, Новосибирск, 1979.

3. В. Визит. Раскраска вершин графа в предписанные цвета // Методы дискретного анализа в теории кодов и схем 29 (1976), 3-10.

4. Н. В. Гравин. Невырожденные раскраски в теореме Брукса // Дискретная математика, 21 (2009), выпуск 4, стр. 106-128.

5. Н. В. Гравин, Д. В. Карпов. Заметка о правильных раскрасках гиперграфов. ПОМИ препринт 2/2010.

6. Д. В. Карпов. Аналог теоремы Брукса для динамических раскрасок. ПОМИ препринт 12/2007.

7. Д. В. Карпов. Динамические правильные раскраски вершин графа. ПОМИ препринт 9/2009.

8. G. Agnarsson and M. M. Halldo'rsson. Strong Colorings of Hypergraphs // Approximation and Online Algorithms Lecture Notes in Computer Science, 2005, Volume 3351/2005, 253-266.

9. S. Akbari, M. Ghanbari, S. Jahanbekam On the dynamic chromatic number of regular graphs. Preprint (presented at BCC22, 2009).

10. S. Akbari, M. Ghanbari, S. Jahanbekam On the list dynamic coloring of graphs // Discrete Appl. Math., vol. 157, 14 (2009) pp. 3005-3007.

11. N. Alon, Z. Bregman. Every 8-uniform 8-regular hypergraph is 2-colorable // Graphs Combinat. 4 (1988), 303-305.

12. N. Alon, J. Spencer. The probabilistic method // Wiley-Interscience, New York, 2000.

13. J. Beck. On a combinatorial problem of P. Erdôs and L. Lovasz // Discrete Math 17 (1977), 127-131.

14. J. Beck. On 3-chromatic hypergraphs // Discrete Math 24 (1978), 127-137.

15. J. A. Bondy, U. S. R. Murty. Graph Theory with Applications // Elsevier, New York, 1976.

16. R. Diestel Graph Theory // Springer, Berlin Heidelberg New York, 2000.

17. P. Erdos. On a combinatorial problem // Nordisk Mat Tidskr 11 (1963), 5-10.

18. P. Erdos. On a combinatorial problem //II Acta Math Acad Sei Hungar 15 (1964), 445-447.

19. P. Erdos, L. Lovasz. Problems and results on 3-chromatic hypergraphs and some related questions // Infinite and finite sets, Colloq. Math. Soc. J. Bolyai, Vol. 10, North Holland, Amsterdam, 1974, pp. 609-627.

20. P. Erdos, A. L. Rubin, H. Taylor. Choosability in graphs // in: Proc. West-Coast Conf. on Combinatorics, Graph Theory and Computing, Areata, California, Congr. Numer. XXVI (1979) 125-157.

21. S.Fan, H.-J.Lai, J.Lin, B. Montgomery, Z. Tao. Conditional colorings of graphs // Discrete Mathematic 16(2006),1997-2004.

22. T. Gallai Kritische Graphen I // Publ. Math. Inst. Hung. Acad. Sei. 8 (1963) p. 373-395.

23. C. Godsil, G. Royle. Algebraic graph theory // Springer 2001.

24. N. Gravin. Time optimal d-list colouring of a graph // CSR 2010: Lecture Notes in Computer Science, vol 6072, Springer 2010, p. 156-168.

25. H. Hind, M. Molloy, B. Reed. Colouring a graph frugally // Combinatorica 17(4) (1997) 469-482.

26. T. R. Jensen, B. Toft. Graph Colouring Problems // John Wiley & Sons, New York, 1995.

27. Kawarabayashi Ken-ichi, B.Mohar. List-color-critical graphs on a fixed surface // Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 1156-1165, New York 2009.

28. A. Kostochka. Coloring uniform hypergraphs with few colors // Random Structures and Algorithms 24 (2004), 1-10.

29. A. Kostochka, M. Stiebitz. A list version of Dirac's Theorem // J. Graph Th. 39 (2002).

30. A. Kostochka, M. Stiebitz, B. Wirth. The colour theorems of Brooks and Gallai extended // Discrete Math 162 299-303 (1996)

31. J. Kratochvil, Z. Tuza, M. Voigt. New trends in the theory of graph colorings: choosability and list coloring // 183-197, DIM ACS Ser. Discrete Math. Theoret. Comput. Sci., 49, Amcr. Math. Soc., Providence, RI, 1999.

32. H.-J. Lai, B. Montgomery, H. Poon. Upper Bounds of Dynamic Chromatic Number // Ars. Combinatoria 68(2003), pp. 193-201.

33. L. Lovasz. On decomposition of graphs // Studia Sci. Math. Hungar. 1 (1966) 237-238.

34. L. Lovasz. Three short proofs in graph theory // J. Comb. Th.(B) 19(1975), 269-271.

35. X Meng, L. Miao, Z. R. Li, B. Sv, The Conditional coloring numbers of Pscudo-Halin graphs // Ars Combinatoria 79(2006), pp 3-9.

36. В. Montgomery. Dynamic Coloring // Ph.D. Dissertation, West Virginia University, 2001.

37. A. Pluha'r. Greedy colorings of uniform hypergraphs // Random Structures and Algorithms 35, (2009) 216-221.

38. B. Reed. A strengthening of Brooks' theorem //J. Comb. Th. (В) V. 76, (1999) p. 136 149.

39. W. M. Schmidt. Ein kombinatoriches problem // Acta Math Acad Sci Hungar 15 (1964), 373-374.

40. S. Skulrattanakulchai A-List Vertex Coloring in Linear Time and Space // Information Processing Letters, Vol. 98 , Issue 3 (May 2006), 101-106.

41. J. H. Spencer. Coloring n-sets red and blue //J Combin Theory Ser A 30 (1981), 112-113.

42. R. Tarjan. Depth-first search and linear graph algorithms // SIAM J. Comput. 1 (2) (1972) 146-160.

43. C. Thomassen. The even cycle problem for directed graphs //J AmMath Soc 5 (1992), 217-229.

44. Z. Tuza. Graph colorings with local constraints—a survey // Discussiones Math. Graph Th. 17(2) (1997), 161-228.47. http://wwwl.spms.ntu.edu.sg/~ngravin/code/Dcols.tgz