Раскраски

Так же, как для графов, вводится понятие вершинной раскраски гиперграфов. Раскраска вершин гиперграфа Н называется правильной, если любое ребро е = EH содер­жит две вершины, окрашенные в различные цвета. Ясно, что правильную раскраску могут допускать лишь гипер­графы, каждое ребро которых имеет степень не меньше чем 2. В этом параграфе рассматриваются только такие типерграфы. Кроме того, будем считать, что изолирован­ных вершин гиперграф не содержит.

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

Хроматическое число χ(H) — это наименьшее число цветов, достаточное для правильной раскраски гиперграфа Н. Если χ(Н)=k, то гиперграф Н называется к-хроматическим.

Очевидно, что разбиению множества VH на независи­мые множества S₁, S₂,..., S_k соответствует правильная раскраска вершин гиперграфа Н k цветами. Верно, конечно, и обратное утверждение.

Теорема 70.1. Для любого гиперграфа Н порядка п справедливы неравенства

где αо(Н) — число независимости гиперграфа Н.

Рассмотрим разбиение множества VH на независи­мые множества S₁, S₂,..., S_k где k = χ(Н). Тогда будем иметь

Отсюда сразу получаем χ(Н)+ α_о(Н)> 2√п

Далее, пусть S — наибольшее независимое множество вершин гиперграфа Н. Окрасим все вершины из S в один цвет и используем п — |S| = п — α_о(Н) других цветов для окрашивания всех вершин из V \ S в разные цвета» В результате получаем χ(Н) + а_о(Н)≤ п+ 1.

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

Так же, как и для графов, через Δ(Н) будем обозна­чать наибольшую из степеней вершин гиперграфа Н:

Абсолютным гиперграфом будем называть гиперграф для любых двух вершин и и v которого существует ребра е = uv. Оказывается, справедлива следующая теорема, яв­ляющаяся обобщением теоремы Брукса (§ 54).

Теорема 70.2 (Л. Ловас, 1968 г.). Если Н — связ­ный гиперграф, отличный от абсолютного, и Δ (Н) ≥ 3, то χ(H) ≤(Н).

Порядком d_H (v) вершины v гиперграфа Н называется мощность наибольшего подмножества E' €EН, |E’| ≥ 2, для любых двух различных ребер е' в е" которого е' ∩ е" = {v}. Если такого подмножества не существует, то по определению d_H(v)= 1.

Теорема 70.3 (И. Томеску, 1968 г.). Пусть S₁, S₂,..., S_k — разбиение множества VH на независимые множества. Тогда

Где

Доказательства двух предыдущих теорем опускаем. Если |Si| = 1 (i = 1, k), то учитывая очевидное нера­венство Δ(Н) ≥ d(H), где d(H)= max d_H(v), получаем

Следствие 70.4. Для любого гиперграфа Н верно неравенство

χ(H) ≤ d(H)+1.

Отсюда сразу имеем (ср. со следствием 54.2) Следствие 70.5. Для любого гиперграфа Н верно неравенство

χ(H) ≤ Δ(H)+1

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

Теорема 70.6. Для любых целых чисел k ≥ 1 и h ≥ 2 существует такой гиперграф Н, что χ(Н)≥ k и |е| ≥ h для любого ребра е € EH.

В качестве такого гиперграфа можно взять h -однородный гиперграф Н, построенный по следующему прави­лу: VH = {v₁, v₂,..., v_n} где n ≥ k(h — 1), ЕH — семей­ство всевозможных подмножеств множества VH мощности h. Поскольку а_о(Н) ≤ h— 1, то на основании теоре­мы 70.1 χ(H)≥n/(h-l), т. е. χ(H)≥ k.

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

Теорема 70.7 (П. Эрдёш, А. Хайнал, 1966 г.). Для любых целых чисел h, k, l≥2 существует h-однородный k-хроматический гиперграф, который не содержит циклов длины меньше l.

Известно, какую роль в теории графов играют бихроматические графы, т. е. графы, хроматическое число которых не превосходит 2. Простой, но очень важный критерий бихроматичности графа дал Д. Кёниг: граф не должен со­держать циклов нечетной длины.

Гиперграф Н тоже будем называть бихроматическим, если χ(H)≤ 2. Для гиперграфа пока не найдено крите­рия бихроматичности в терминах его структуры.

Утверждение 70.8. Если гиперграф не содержит циклов нечетной длины, то он является бихроматическим.

Доказательство проводим по той же схеме, что и доказательство теоремы 9.1, предполагая, что гиперграф

связен. А именно, сначала окрасим произвольную верши­ну v гиперграфа Н в красный цвет, затем произвольную вершину и, отличную от v, окрасим в красный цвет, если расстояние d(u, v) — четное число, и в синий цвет, если это расстояние нечетно. Если Н — не бихроматический гиперграф, то найдутся две смежные вершины и и w, ок­рашенные в один цвет, а тогда легко обнаруживается цикл нечетной длины.

Как показывает пример гиперграфа, изображенного на рис. 70.1, условие утверждения 70.8 не являются необхо­димыми.

Более широкий класс бихроматических графов нашли Фурнье и Лас Верньяс. Этот результат приведем без до­казательства.

Теорема 70.9 (Ж. Фурнье, М. Лас Верпьяс, 1972). Если в каждом цикле нечетной длины гиперграфа Н есть три ребра, имеющие общую инцидентную вершину, то гиперграф Н является бихроматическим.

Пример гиперграфа на рис. 70.1 показывает, что это достаточное условие также не является необходимым.

Непосредственно из теоремы Кёнига следует

Утверждение 70.10. Если гиперграф является бихроматическим, то он не содержит ни одного цикла нечетной длины, состоящего лишь из ребер степени 2.

Пример гиперграфа, изображенного на рис. 70.2, пока­зывает, что обратное утверждение неверно.

Доказательства теорем, опущенные в этом парагра­фе, можно найти в [20].