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

• Гравин, Николай Вадимович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Гравин, Николай Вадимович

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(У) в к цветов.

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

Список литературы диссертационного исследования кандидат физико-математических наук Гравин, Николай Вадимович, 2010 год

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