Если С = (V, Е) — граф, то будем обозначать через:
п(С) = |У'| — число вершин (7, а т(С) = \Е\ — число ребер;
если М с V, то Є(М) — индуцированный подграф С, определяемый множеством М;
(іс(х) (степень тишины графа) — количество ребер, содержавших вершину X Є С\
<1(С) (степень графа) максимальная из степеней вершин;
о;((7) (кликовое число графа) — число вершин в наибольшей клике;
\(С) — хроматическое число О, то есть минимально возможное число цветов по всем правильным раскраскам С;
Хтлг((1,ш) — максимальное возможное хроматическое число графа степени (І с кликовым ЧИСЛОМ и)\
О — дополнительный і-раф к графу С — (У9Е)\
Е(О) индуцированный подграф С, множество вершин которою совпадает с пересечением всех максимальных но мощности клик графа
С;
Т(<7) — индуцированный подграф (7, множество вершин которого совпадает с объединением всех максимальных по мощности клик графа С.
Введение.
Теория графов является одним из важнейших и интереснейших разделов математики. В различных областях математики - алгебре, топологии, информатике и других — возникает потребность описания свойств тех или иных объектов на языке теории графов и использования результатов теории графов, что подчеркивает значимость изучения графов и их свойств.
О<-
1
Одним из важнейших и сложнейших направлений исследований в теории графов является изучение хроматических чисел различных графов. Хроматическим числом графа называется наименьшее натуральное число п такое, что граф допускает правильную окраску в п цветов, но не допускает правильную окраску в меньшее количество цветов. Правильной называется такая окраска вершин графа, при которой смежные вершины имеют различные цвет. Одним из наиболее классических результатов в этой области является теорема Брукса, утверждающая, что хроматическое число графа степени п, максимальная клика которого имеет мощность и. равно п. Это утверждение перестает быть верным, если степень графа увеличить до п 4- 2. Bruce Reed в 1998 году доказал, что для достаточно больших п степень графа в формулировке теоремы Брукса можно увеличить до п 4- 1(См. |18|).
Также было получено множество результатов, связывающих степень графа и его хроматическое число с размером максимальной клики. В частности, хотелось бы отметить статью |31|, в которой доказано, что существует раскраска графа G степени /? с со{С) < п 4- 1 в v цветов, в которой максимальная антиклика монохроматична и результат А. В. Косточки |22] установившего, что если (1{G) — u>(G) > min{0(rrf((7)1/',),0(r2)}, то *(G) < d(G) ~~г-
Многие исследования были посвящены обобщению теоремы Брукса для различных классов графов, например в статье [34| теорема обобщена на случай графа, не содержащего данного дерева на п 4- 2 вершинах: доказано, что в этом случае степень графа тоже может быть увеличена до п 4-2 для любого п, при этом размер максимальной клики и хроматическое число тоже будут равны п. Также немало усилий было приложено к поиску алгоритмов нахождения правильной окраски графов, например алгоритм Grotachel, Lovasz и Sehrijver для окраски совершенного графа за полиномиальное время или алгоритм Карлоффа |35) окраски
2
графа, степени п без Кп+ Особое место занимает исследование сильного хроматического числа графа, связанного с его разбиением на равномощные множества, вершины которых затем окрашиваются в различные цвета. Оценки, связывающие такие хроматические числа со степенью графа были получены в |2| и развиты в [3], но сути эти исследования сводятся к получению оценок на хроматические числа слоистых графов, т. е. графов, разбивающихся на равномощные клики. В дальнейшем, в статье |6| была получена точная оценка, на степень слоистого графа, допускающего правильную окраску в количество цветов, равное размеру максимальной антиклики, но только для случая не более, чем трех слоев.
Еще одним популярным направлением исследований являются исследования гра<)юв клик, в частности, графов с условием Хелли па клики (Clique-Helly graphs). Обзор результатов по этой тематике можно найти в [13|. В статье |14| было получено описание некоторого вида графов, которые могут быть графами клик для других графов. Оказалось, что таковыми являются именно те графы, которые обладают свойством Холли для клик. В дальнейшем этот результат был обобщен в статье |15|.
3
Глава 1.
Теорема Хелли для клик.
Графы клик изучаются уже даймо и многие результаты стали классическими. Важное место в этой теории занимают графы с условием Хелли на клики (СНсріе-НеНу ^гаріїв), т. е. графы, в которых любой набор попарно пересекающихся максимальных (но количеству вершин) клик имеет общую для всех этих клик вершину. Ряд результатов на эту тему изложен в работе |13|.
В этой главе будет рассмотрена связь между степенью графа и размером максимальной клики и будет выведено простое соотношение, позволяющее определить значительный класс графов с условием Хелли на клики (см. теорему 1 и следствие 3).
Лемма 1. 1 Пусть число вершин в графе (7 не превосходит 2п— 1, а после удаления любой вершины найдется клика мощности п. Тогда в графе С сеть клика мощности п 1.
Доказательство. Предположим противное. Рассмотрим минимальное п, для которого не выполняется утверждение леммы и граф О — контрпример для п. Пусть в этом графе 2п — Ь вершин. Пусть Я — дополнение графа С. Вес дальнейшие рассуждения будут проводиться с грифом Н. Рассмотрим любую антиклику этого графа, содержащую п вершин (т. е. п-клику в С). Множество ее вершин обозначим через -V, а множество остальных вершин — через У. Назовем подмножество М С У плохим, если оно либо пусто, либо количество вершин в М больше количества вершин в X, смежных хотя бы с одной вершиной из М. Обозначим через /1 максимальное плохое подмножество У (оно
‘Эт лемма н несколько ином ъиде истрегилась в статье [12). В настоящем виде автору ее сообщил 13. Л. Дольников.
4
может быть н пустым), а через В' —множество вершин из X, смежных с вершинами из А. Пусть |Л| = к. Тогда двудольный граф с долями У\4н X \ В' и ребрами графа Я между этими долями будет удовлетворять условию теоремы Холла (см. |6() (иначе А — но будет максимальным плохим подмножеством), поэтому каждой вершине У\А можно поставить в соответствие смежную с ней вершину X \ В' таким образом, чтобы все эти смежные вершины были различны. Множество недопоставленных вершин X обозначим через В. Ясно, что В содержит ровно к + / вершин. Рассмотрим грае)) Я', образованный вершинами АиВ и ребрами графа Я, соединяющими эти вершины. Заметим, что при удалении любой вершины из II' в графе II должна была найтись антиклика с п вершинами, но в нее могло входить не более, чем и — к — 1 вершин из (X и У) \ (АиВ), так как вершины этого множества разбиты ровно на п — к — /, пар смежных. Следовательно, остальные к + 1 вершин должны быть из Ли Я. Поэтому в Я' после удаления любой вершины найдется антиклика с к-\-1 вершинами. Тогда либо либо А = У, либо в Н' найдется антиклика с /с-Н-Н вершинами в силу минимальности а, поскольку |Я'| = 2/с + I < 2(к + /) — 1. Во втором случае заметим, что при добавлении к вершинам этой антиклики всех вершин из X \ В получим антиклику с п + 1 вершинами. В первом случае в графе С найдется вершина, смежная со всеми остальными (это любая вершина из X \ В'). Отбросим ее, тогда по условию найдется клика с п вершинами. Добавляя к ним отброшенную, получим клику с п + 1 вершинами. Полученное противоречие доказывает утверждение леммы. □
Лемма 2. Если о некотором графе С /максимальная клика имеет мощность п и при этом найдется набор попарно пересекающихся 71-клик, не имеющих общей вершины, то в этом графе не менее 2п вершин.
Доказательство. Предположим, что утверждение леммы не
- Київ+380960830922