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

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

Берлов Сергей Львович

ХРОМАТИЧЕСКИЕ ЧИСЛА СЛОИСТЫХ ГРАФОВ

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

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

003460148

Ярославль - 2008

003460148

Работ* выполнена на кафедре теории функций и функционального апнлнча Ярославского государственного университете им. П. Г. Демидова

Мяу ч о ый ру ко вод! ггеяь

.......доктор физико-математических наук, ¡трофг сор

Дольников Владимир Леонкдонпч

Официальные оппоненты:

— доктор физико-математических наук, профессор

Тимофеев Евгений Анатольевич

— доктор физико-математических наук, профессор

Райгородский Андрей Михайлович

Ведущая организация ..... Санкт-Петербургское отделение

Математического института нм. В. А. Стеклова Российской Академии Наук

Защита диссертации состоится 13 февраря 200!) год» в час. на

заседании Диссертационного совета Д 212.002.03 при Ярославском государственном университете имени П. Г. Демидова по адресу: 150008 г. Ярославль, ул. Союзная, д. 144. аудитория 426.

С диссертацией можно ознакомиться в библиотеке Ярославского го-., сударствешюго университета им. П. Г. Демидова

Автореферат разослан " ^ " 2009 года.

Ученый секретарь диссертационного совета у- С.И. Яблоко;«!.

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

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

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

Одним из классических результатов в этой области является теорема БрукаI, доказанная в (lj, которая утверждаег, что хроматическое число графа степени п, максимальная клика которого имеет мощность п. равно п при п >- 3. Это утверждение перестает быть верным, если степень графа увеличить до п + 2. В. Reed в 1008 году доказал, что для достаточно больших п степень графа в формулировке теоремы Брукса можно увеличить до п + 1 (¡2|).

Многие исследования были посвящены обобщению теоремы Брукса /!дя различных классов графов, например в статье [5] теорема обобщена на случай графа, не содержащего данного дерева на п+2 вершинах: доказано, что в этом случае, степень графа тоже может быть увеличена до п +1 для любого п, при этом размер максимальной клики и хроматическое число тоже будут равны п.

Было получено множество результатов, связынающих степень графа и его хроматическое число с размером максимальной клики. В частности^. хотелось бы отметить статью |3]. в которой доказано, что существует раскраска графа G степени п к m(G) < п + 1 в п цветов, в которой максимальная аитиклика монохроматична и результат А. В. Косточки |4|

установившего. что если d(G) — u>(G) > min{(?(rd(G)I//4),0(г2)}, то X(G) < d(C) - r.

Немало усилий было приложено к попеку алгоритмов нахождения правильной окраски графов, например алгоритм Grotachel, Lovasz и Schri-jver для окраски совершенного графа за полиномиальное время или алгоритм Карлоффа [6] окраски графа степени п б ез Кп+%.

Особое мести занимает исследование сильного хроматического числа графа, связанного с его разбиением на равномощные множества, вершины которых затем окрашиваются в различные цвета. Оценки, связывающие такие хроматические числа со степенью графа, были получены в [7] и развиты d |8[. По сути эти исследования сводятся к получению оценок на хроматические числа слоистш; графов, т. е. графов, разбивающихся на рав но мощные кли к и.

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

Еще одним популярным направлением исследований являются исследования графов клик, в частности, графов с условием Хелли на клики (Cliquo-HelLy graphs). Обзор результатов по этой тема/гике можно найти в [10). В статье [11} было получено описание некоторого вида графов, которые могут быть графами клик для других графов. Оказалось, что таковыми являются именно те графы, которые обладают свойством Хелли для клик. В дальнейшем этот результат был обобщен в статье [12].

Таким образом, тематика диссертации находится в русле современных тенденций развития науки и является актуальной.

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

Холл и для я-клик.

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

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

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

2. Предложен алгоритм нахождения независимой траисверсали, пересекающей все максимальные клики. Доказано существование такой траисверсали для графов степени, не превосходящей н + к, при

п > 2(А:+1), где п.......размер максимальной клики. Этот алгоритм применен

для доказательства критерия п-хроматичности графов специального вида, называемых, слоистыми, т. е. таких, которые разбиваются на непересекающиеся п-клики. Оказывается, что все п-слоистые графы степени п + к являются п-хромати'шыми. еслп п > 3(к 4-1).

3. Рассмотрены вопросы нахождения хроматических чисел п-слоистых графов при условии отсутствия в них п + 1-клик. Получена точная оценка для трехслойных графов, получены достаточно точные верхние оценки дли пяти- и семислоГшых графов, а также выведена общая формула для верхней оценки хроматического числа графа с любым количеством слоев,

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

числа графа чср<г.> количество ^-критических подграфов, покрывающих его вершины, также получен аналогичный результат для слоистых графов.

Научная новизна. Все основные результаты диссертации являются новыми.

Практическая и теоретическая ценность. Работа носит теоретический характер. Результаты работы могут быть использованы для получения верхних оценок на хроматические числа различных классов графов в зависимости от размера их максимальной клики. Алгоритм из главы 2 может быть применен и в других ситуациях, его универсальность продемонстрирована в главе 3. Разбиение на орбиты, использованное, в глав« 4, позволяет работать со многими классами графов, разбивающихся на циклы. Методика, примененная в пятой главе, позволяет получать верхние оценки иа хроматические числа графов и различных ситуациях, некоторые из которых проиллюстрированы в работе.

Апробация работы. Результаты диссертации докладывались на семинаре по дискретной математике ПОМИ РАН и на Восьмом Международном семинаре "Дискретная математика и ее приложения" (Москва, МГУ, 2004).

Публикации. Основные результаты диссертации изложены в работах [19] и ¡21], перечисленных в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав и списка литературы. Нумерация разделов, формул, замечаний, лемм, теорем и определений -- сквозная. Текст диссертации изложен на 82 страницах (исключая список литературы). Список литературы содержит 40 наименований.

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

Первая глава диссертации посвящена графам с условием Хслли на клики.

Введем необходимые обозначения.

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

п(С) = IV'!.......число вершин 6\ ичп(О') = |£| - число ребер;

если М С V, то С{М).......индицированный подграф 6", определяемый

множеством М;

(}.(;{х) (степень вершины графа) количество ребер, содержащих вершину х 6 0\

<1{0) (степень графа).......максимальная из степеней вершин;

¡¿(С) (кликовое число графа) - число вершин в наибольшей клике; хроматическое число С, то есть минимально возможное число цветов но всем правильным раскраскам С;

ХтаЛ(1.и.>) максимальное возможное хроматическое число графа степени д. с кликовым числом

О........дополнительный граф к графу С — (V. Е);

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

Т(С) — индуцированный подграф С, множество вершин которого совпадает с объединением всех максимальных по мощности клик графа О.

К».......полный граф па п вершинах.

Базовой является следующая .лемма;

Лемма 1. Пусть п(С) 2п — 1. а погас удаления любой иершипы найдется клика мощности п. Тогда в графе С есть клика мощности п+1.

Эта лемма в несколько ином виде встретилась в статье |13). В настоящем виде автору со сообщил В. Л. Дольников. В работе приведено простое авторское доказательство этой леммы. Из этой леммы можно вывести ряд интересных результатов:

Теорема 1. Пусть в графе G uj{G) ■ — п. d(G) < f§n] — I, « любые две п-клит имеют общую вершину. Тогда и все. п-клики имеют общую вершину.

Это основная теорема первой главы. Она дает оценку на степень графа для того, чтобы в графе выполнялось свойство Хелли для п-клик.

Оценка f|n] — 1........точная, в работе приведен пример графа, в котором

3п - 3[n/3j вершин и существуют три попарно неперш,"кающиеся клики, не содержащие общей вершины.

Обобщением теоремы 1 является следующее утверждение:

Теорема 2. Пусть w(G) = п. <1{G) < f|n] - 1, и задан некий набор попарно пересекающихся п-клик. Тогда все п-клики этого набора имеют более п/3 общих вершин.

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

Во второй главе утверждения теорем 1 и 2 применяются для доказательства следующей теоремы:

Теорема 3. Пусть G ...... такой граф. что uj(G) = п, do < п + к, и

п > 2(к + 1). Тогда существует независимое подмножество M С V

такое, что при удалении из -графа всех вершин M размер максимальной ■клики уменьшится.

В работе приводится алгоритм поиска такого подмножества, называемого также трапсверсалью.

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

Из теоремы 3 можно извлечь важное следствие: Следствие 1. Если d < — 2], то выполняется неравенство

XiMz{d,u) - 1 < Xuuaid- 1,и> - 1).

Это следствие даст новею соотношение между максимальным хроматическим числом графа, размером максимальной клики и степенью.

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

Эта задача в несколько иных терминах была поставлена Н. Алоном в 1992 году' в [7|. Им была получена весьма грубая оценка па степень такого графа, при которой граф допускает правильную раскраску и » цветов. В дальнейшем эта оценка была существенно улучшена в статье Р. Нах-ell [8]. В третьей главе, получено неравенство, из которого будет следовать, в частности, общая оценка P. Haxell, а также улучшение этой оценки на случай небольшого числа слоев.

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

Для таких графов доказана следующая теорема:

Теорема 4. Пусть G такой п-саожтый граф, что |V(G)| = nq, d{G) < п + к, причем (3(k + 1) — n)q < 2k + 1, Тогда G является п-хролтпичтш.

Кроме того, получен новый критерий п-хроматичностн графов:

Следствие 2. Пусть G такой граф, что его вершины, люжпа разбить па непересекающиеся не более., чем п-элементнш множества j4j. Лг, • • • -4» таким образом, что внштш степени всех вершт не. превосходят ^тр. Тогда этот араф п-хроматичеи.

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

А, к роме самой А. Теорема 4 также позволяет улучшить эту оценку для небольших значений л-.

При п ^ 6 можно усилить этот результат в близком классе графов:

Определение 2. Граф С! будем называть бинарным, если его вершины можно разбить на множества, удовлетворяющие следующим свойствам:

1. Каждое множество состоит из одной или двух вершин.

2. Любая вершина О смежна с. вершинами только одного множества кроме того, в котором она лежит.

Такое разбиение будем называть специальным.

Лемма 2. Пусть граф С, обладает следующим свойством: существует такой остовпый подграф (п. который сам является бинарным и при удалении всех ребер 0\ оставшиеся ребра образуют бипарный граф Со-Тогда С является 4-хроматичным.

Из леммы 2 выводится следствие:

Следствие 3. Рассмотрим 4-олоистый граф С степени 5. Пусть после удаления всех внутренних ребер всех слоев оставшийся граф не будет содержать нечетных циклов длины более .9. Тогда граф О является 4-хромтпичным.

Четвертая глава посвящена проблеме, поставленной в ¡18]. Она заключается в нахождении хроматических чисел п-слоистых графов без ограничений на степень, но с ограничением на мощность максимальной клики, равную п. Сама но себе проблема трудна и тесно связана с получением верхних и нижних оценок чисел Рамсея. В работе удалось добиться существенных продвижений. Во-первых, была получена оценка сверху для п-елоистых графов па пк вершинах , которая оказывается достаточно точной, как следует из следующей леммы:

Лемма 3. Для любого натурального к существует натуральное п — п(к) и такой п-слочстый граф 6" с кп «ершиками, что и/(<2) = п, а \(в)>кп/2- (к~~1)2Ь2п.

Получснная оценка снизу для четных к при больших п очень близка к верхней оценке.

Нечетный случай намного сложнее. Получаемую из естественных соображений оценку можно существенно улучшить.

Теорема 5. Пусть в п-можтом, -графе С кп вершин, где. к — нечетное, число, большее девяти. Пусть ы(б') = «. Тогда х(<?) < ^(1 + ЩьЩ).

Для доказательства применен метод разбиения на множества специального вида. называемых в работе орбитами. Удалось получить точную оценку при к = 3.

Теорема 6. Пусть в п-слоистом графе. С на 3п вершинах «(С?) = п. Тогда х(С) < |п.

В работе приведен пример, когда, эта оценка достигается для любого п, кратного пяти. Для построения примера использовались компьютерные оценки для чисел Рамсея Язи-

В работе были доказаны достаточно точные оценки при к = 5 и к = 7, для получения которых также были применены результаты компьютерных исследований чисел Рамсея:

Теорема 7. Пусть в п-слоистом графе. С Ъп вершин, причем «(<?) = п. Тогда х(С) < Цп.

Теорема 8. Пусть о п-слоистом графе С Та вершин, причем и»(С?) — п. Тогда х(в) 4 Ц«.

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

Теорема 9. Пусть С граф. Даны натуральные числа щ < <Н <"•< а»: такие, что ^ = п(С). причем длина минимального нечетного цикла С? больше щ и (1(0) < — 1. Тогда ае.ршины С можно правильно

окрасить в к цветов так, что будет рояно а, вершин цвета г.

Из этой теоремы следует результат, касающийся равномерных правильных раскрасок. т. е. таких, в которых всех цветов поровну:

Следствие 4. Пусть пик ....... натуральные числа. Граф G таков, что

n(G) — nk и d(G) < k — 1 , щтчем все печатные циклы G содержат более п вершин. Тогда его вершины можно правильно окрасить в А- цветов так. что вершин, окрашенных в каокдий цвет будет ровно п.

Напомним, что граф G называется к~критиче.с.тли если его хроматическое число равно к, а любой его собственный подграф к— 1-хроматнчен (см ¡14]), Заметим, что любой критический граф конечен в силу теоремы Де БреОна-Эрдеша [15].

Определение 3. Пусть х.......вершина графа G. Будем обозначать черта

degcjt{x) количестно всех ¿-критических подграфов G' С G таких, что х е G". Если & = 2, то degc^j(a?).......это степень вершины х графа G.

Определение 4. Граф G будем называть (к,Н)-вырожденным, если любой его подграф Н содержит такую вершину х € V'(tf). что

<!i;g//„tM -i д.

Тогда верна следующая теорема, доказанная в работе методом одновременной перекраски:

Теорема 10. Пусть 6"о.......подграф G и прсдпаножим, что любой подграф

Н, удовлетворяющий условиям Go С Н С С, V(G<)} ф V(H) содержит такую вершину х € Н — б'о, чти dngGik(x) < d. Пусть ,*> — натуральное число и t — max{«,x(<?o)}- Если С*"1 > d, тогда \{G) si t

Эта теорема обобщающает классические результаты: теоремы Кенига ¡10] и теоремы Вильфа-Секергала jl7}.

Аналогичные идеи нриложвмы и к раскраскам слоистых графов. Только необходимо несколько изменить формулировку, поскольку в слоистых графах достаточно много ¿-критических подграфов, лежащих целиком или почти целиком в одном слое.

Определение 5. ¿-критический подграф графа С будем называть важным, еади em пересечение с любым слоем содержит не более к — 1 вершин.

Тогда верна следующая теорема:

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

к-критиче.с.кими подграфами. Тогда x(G) = п.

Список литературы

(1] R. L. Brooks Оа coloring the nodes of a network / Brooks R. L. // Proc. Cambrige Phil......1941 - Soc 37 - P. 194-197.

[2J Reed B. A Strengthening of Brooks' Theorem /В. Reed // Journal of Combinatorial Theory, Series В 1999 V. 76 -■■ Issue 2 - P. 13G.....149.

[3j Catlin P. Brooks' graph-coloring theorem and the independence number.

/Р. Catlin // Journal of Combinatorial Theory, Series В..... 1979 - V.27 -

P. 42-48.

[4| Kostochka, A. V. Degree, density and chromatic number of graphs./ A. V. Kostochka // Melody DLskret. Analiz. - 1980 - No. 35- P. 45-70,104-105.

[5J Mihok P. An extension of Brooks' theorem. /Р. Mihok // Ann. Discrete Math. - 1992 - 51 .....North-Holland, Amsterdam.

[6] KarloiF. Howard J. An NC algorithm for Brooks' theorem./ Howard J. Karloff // Theoret. Comput. Sci. - 1989 V. 68 - no. 1 P. 89-103.

{7j Alon N. The strong chromatic number of a graph./ N. Alois // Random Struct. Aki. 1992 - V. 3 P. 1 7.

[8) Haxcll P. E. On the Strong Chromatic Number / P. E. Haxcll // Combinatories, Probability and Computing, - 2004 - Vol. 13 -- Issue С - P. 857 - 865.

[9] Axenovich M., Martin R. On the Strong Chromatic Number of Graphs / M. Axenovich, R. Martin // SLAM Journal on Discrete Mathematics archive - 2006 V. 20 Issue 3 P. 741 ..... 747.

]1()| Farrugia, A. Clique-Helly graphs and hereditary clique-Holly graphs, a mini-survey. / A. Farrugia // Algoritrnic graph t.heory(CS 762) - 2002 -Projeet, Dept. of Combinatorics, University of Waterloo.

[11] Hamelink R. A partial characterization of clique graphs./R. Hamelink (f Journal of Combinatorial Theory, Ser. В • 1968.....V. 5.....P. 192-197.

[12| Roberts F. and Spencer J. Characterization of clique-graphs./ F. Roberts and J. Spencer // Journal of Combinatorial Theory, Ser. В 1971 -■ V. 10 - P. 102-108.

[13| Erdös P. and Gallai T. On minimal number of vertices representing the edges of a graph./P. Erdös and T. Gallai //Publ. Math. Inst. Hung. Acad, Sei 1961 V. 6 P. 89-96.

[14] Dirac G.A. A property of 4-chromatic graphs and some remarks on critical

graphs./G.A. Dirac // Journal London Math. Soc. .....1952 V. 27 ■ P.

85-02.

¡15] de Brmjn and Erdös P. A colour problem for infinite graphs and a problem in the theory of relations. / de Bruijn and P. Erdös // Nederl. Akad. Weteusch. Proc. Ser. A - 1951.....V. 54 P. 371 ..... 373.

[16] König D. Uber Graphen und ihre Anwendung auf Determinantenthmric und Mengenlehre./D. König // Math. Ann......1916 - V. 77 P. 453-465.

|17| Szekeres G. and Wilf U.S. An inequality for chromatic number of a graph /G. Szekeres arid H.S. Wilf// Journal of Combinatorial Theory, Series B.

1908 V. 4 - P. 1-3.

}IS] Дольников В.Л. Об одной задаче окрашивания /В.Л. Дольников /./ Сиб. мат. жури. Т. 13 -■ 1972 № 6. С. 1272-1281.

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

Статьи в »зданиях, включенных в перечень ВАК РФ:

[19] Берлов С. Л. Свойство Хелли для n-клик и степень графа. / С. Л.

Берлов // Записки научных семинаров ПОМИ..... 2006 - Т. 340 С. 5

9.

|20] Берлов С. Л. Соотношения между кликовым числом, хроматическим числом и степенью для некоторых видов графов. / С. Л. Берлов //'

Моделирование и анализ информационных систем..... 2008 - Т. 15.....Н.

4.....С. 10-22.

[21] Berlov S. L., DoPnikov V. L. Some generalization of theorems on a vertex colouring / S. L. Berlov, V. L. Dol'iiikov //Joiirnal of Combinatorial Theory Ser. A - 2006 V. 113 - Issue 7 - P. 1582 - .1585

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

[22j Берлов С. Л. Соотношения между кликовым числом, хроматическим числом и степенью для некоторых видов графов. / С. Л. Берлов // Препринт ПОМИ РАН 2008 - Н. 24 • 11 с.

Подписано в печать 29.12.08. Формат 60x84/16. Усл. печ. л. 0,93. Тираж 100. Заказ № 90

Типография Издательства СПбГУ. 190066, Санкт-Петербург, Средний пр., 41

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

Одним из важнейших и сложнейших направлений исследований в теории графов является изучение хроматуческих чисел различных графов. Хроматическим числом графа называется наименьшее натуральное число п такое, что граф допускает правильную окраску в п цветов, но не допускает правильную окраску в меньшее количество цветов. Правильной называется такая окраска вершин графа, при которой смежные вершины имеют различные цвета. Одним из наиболее классических результатов в этой области является теорема Брукса, утверждающая, что хроматическое число графа степени п, максимальная клика которого имеет мощность ?/, равно п. Это утверждение перестает быть верным, если степень графа увеличить до п + 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].

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.