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

• Берлов, Сергей Львович
• кандидат физико-математических наук
• 2008

Введение диссертации (часть автореферата) на тему «Хроматические числа слоистых графов»

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

Одним из важнейших и сложнейших направлений исследований в теории графов является изучение хроматуческих чисел различных графов. Хроматическим числом графа называется наименьшее натуральное число п такое, что граф допускает правильную окраску в п цветов, но не допускает правильную окраску в меньшее количество цветов. Правильной называется такая окраска вершин графа, при которой смежные вершины имеют различные цвета. Одним из наиболее классических результатов в этой области является теорема Брукса, утверждающая, что хроматическое число графа степени п, максимальная клика которого имеет мощность ?/, равно п. Это утверждение перестает быть верным, если степень графа увеличить до п + 2. Bruce Reed в 1998 году доказал, что для достаточно больших п степень графа в формулировке теоремы Брукса можно увеличить до п + 1(См. [18|).

Также было получено множество результатов, связывающих степень графа и его хроматическое число с размером максимальной клики. В частности, хотелось бы отметить статью [31|, в которой доказано, что существует раскраска графа G степени п с co(G) < п + 1 в 71 цветов, в которой максимальная антиклика монохроматична и результат А. В. Косточки [22] установившего, что если d(G) — lo{G) > min{OHG)1/'1), 0(r2)}, то x(G) < d(G) - r.

Многие исследования были посвящены обобщению теоремы Брукса для различных классов графов, например в статье [34] теорема обобщена на случай графа, не содержащего данного дерева на п + 2 вершинах: доказано, что в этом случае степень графа тоже может быть увеличена до п + 2 для любого п, при этом размер максимальной кликп и хроматическое число тоже будут равны п. Также немало усилий было приложено к поиску алгоритмов нахождения правильной окраски графов, например алгоритм Grotschel, Lovasz и Schrijver для окраски совершенного графа за полиномиальное время или алгоритм Карлоффа [35] окраски графа степени п без Кп+\. Особое место занимает исследование сильного хроматического числа графа, связанного с его разбиением на равномощные множества, вершины которых затем окрашиваются в различные цвета. Оценки, связывающие такие хроматические числа со степенью графа были получены в |2] и развиты в [3], по сути эти исследования сводятся к получению оценок на хроматические числа слоистых графов, т. е. графов, разбивающихся на равномощные клики. В дальнейшем, в статье [6] была получена точная оценка на степень слоистого графа, допускающего правильную окраску в количество цветов, равное размеру максимальной антиклики, но только для случая не более, чем трех слоев.

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

Список литературы диссертационного исследования кандидат физико-математических наук Берлов, Сергей Львович, 2008 год

1. FarruGIA, A.(2002) Clique-Helly graphs and hereditary clique-Helly graphs, a mini-survey. Algoritmic graph theory(CS 762), Project, Dept. of Combinatorics, University of Waterloo.

2. HAMELINK R.(1968) A partial characterization of clique graphs. Journal of Combinatorial Theory, Ser. B, 5, 192-197.

3. BROOKS R,. L.(1941) On coloring the nodes of a network. Proc. Carn-brige Phil. Soc 37, 194-197.

4. REED B. (1999) A Strengthening of Brooks' Theorem. Journal of Combinatorial Theory, Series B, Volume 76, Issue 2, July 1999, Pages 136-149

5. Jensen Т., Toft B.(1995) Graph coloring problems., Wiley-Interscicnce Series in Discrete Mathematics and Optimization.

6. TATT У.1988 Теория графов., гл. 2 пар. 6, Теорема Холла, изд. "Мир".

7. O. Borodin and A. Kostochka(1977) On an upper bound on a graph's chromatic number, depending on the graphs's degree and density. J.Comb.Th.(B) 23, 247 250.

8. KONIG D.(1916) Uber Graphen und Hire Anwendung auf Determinantentheorie und Mengenlehre. Math. Arm. 77 453 465.

9. Kim, Jeong Han(1995)On Brooks' theorem for sparse graphs. Combin. Probab. Cornput. 4, no. 2, 97-132.