Гипотеза Хивуда

Определение:

Хроматическим числом поверхности поверхности [math]S_n[/math] или [math]n[/math]-ым числом Хивуда называется число [math]\chi \left( S_n \right)[/math], равное максимальному хроматическому числу графа, который можно уложить на поверхность [math]n[/math]-ого рода.

Теорема о нижней границе хроматического числа поверхности

Теорема (Теорема Рингеля и Янгса):

Для любого положительного целого числа [math]n[/math] хроматическое число поверхности [math]n[/math]-ого рода [math]\chi \left( S_n \right) \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right][/math].

Доказательство:

[math]\triangleright[/math]

Воспользуемся формулой Эйлера [math]V + F - E = 2 - 2n[/math]. Давайте докажем нижнюю границу на [math]E[/math]. Максимизируем число граней: каждая из них может быть треугольником. Тогда для [math]E[/math] существует неулучшаемая нижняя граница: [math]E \geqslant 3 \left( V - 2 + 2n \right)[/math] [math]n \geqslant \dfrac{1}{6} E - \dfrac{1}{2} \left( V - 2 \right)[/math]. Рассмотрим полный граф [math]K_p[/math], тогда получаем, что [math]\gamma \left( K_p \right) \geqslant \dfrac{1}{6} \dfrac{p (p - 1)}{2} - \dfrac{p - 2}{2}[/math] [math]\gamma \left( K_p \right) \geqslant \left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}[/math], функция монотонно возрастает при [math]p \geqslant 4[/math], и для любого [math]n[/math] наибольшее значение функция [math]\left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}[/math] достигается при [math]p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right][/math]. Поскольку [math]\chi\left(K_p\right) = p[/math], откуда получаем, что [math]\chi \left( S_n \right) \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right][/math].

[math]\triangleleft[/math]

Теорема о верхней границе хроматического числа поверхности

Теорема (Гипотеза Хивуда):

Для любого положительного целого числа [math]n[/math] хроматическое число поверхности [math]n[/math]-ого рода [math]\chi \left( S_n \right) \leqslant \left[ \dfrac{ 7 + \sqrt{1 + 48n} }{ 2 } \right][/math].

Доказательство:

[math]\triangleright[/math]

Пусть задан граф [math]G[/math] с [math]V[/math] вершина, [math]E[/math] рёбрами и [math]F[/math] гранями, также будем считать, что [math]G[/math] — триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности [math]n[/math]-ого рода). Обозначим за [math]d[/math] — среднюю степень вершины графа [math]G[/math], тогда должно быть справедливым следующее равенство: [math]dV = 2E = 3F[/math] Воспользуемся формулой Эйлера [math]V - E + F = 2 - 2 n[/math], откуда [math]E = V + F + 2 (n - 1)[/math] и [math]F = 2 V + 4 (n - 1)[/math] и подставляя в первое равенство получаем [math]dV = 6V + 12(n - 1)[/math] [math]d = 6 + \dfrac{12(n - 1)}{V}[/math] Поскольку [math]d \leqslant V - 1[/math], то [math]V - 1\geqslant 6 + \dfrac{12(n - 1)}{V}[/math] Найдём единственный положительный корень неравенства [math]V \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right][/math] Обозначим за [math]H(n) = \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right][/math]. Если [math] V \leqslant H(n)[/math], то тогда граф [math]G[/math] очевидно можно раскрасить в [math]H(n)[/math] цветов и неравенство верное. Допустим, что [math]V \gt H(n)[/math], тогда [math] d \lt 6 + \dfrac{12(n - 1)}{H(n)} = H(n) - 1[/math] Значит в такое графе существует хотя бы одна вершина степени не больше [math]H(n) - 2[/math], стянем её с любой соседней и получим новый граф [math]G'[/math] с [math]V - 1[/math] вершинами. Если [math]V - 1 = H(n)[/math], то граф [math]G'[/math] можно раскрасить в [math]H(n)[/math] цветов, значит и сам граф [math]G[/math] можно также раскрасить в [math]H(n)[/math] цветов, если [math]V - 1 \gt H(n)[/math], то опять найдём вершину степени [math]H(n) - 2[/math] и снова стянем её и будем продолжать так до тех пор, пока не получим желаемый граф.

[math]\triangleleft[/math]

Из всего выше сказанного получаем, что [math]\chi \left(S_n\right)[/math] в точности равно [math]\left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right][/math].

Проблема четырёх красок

Заметим, что теорема Хивуда не работает при [math]n = 0[/math], поэтому проблема четырёх красок не может быть доказана с помощью этой теоремы, однако при подстановке [math]n = 0[/math] получаем [math]\chi \left( S_0 \right) = 4[/math].

См. также

• Хроматическое число планарного графа
• Проблема четырёх красок
• Формула Эйлера

Источники информации

• Wikipedia — Heawood conjecture
• Последовательность чисел Хивуда
• Ф.Харари «Теория графов» — М.: Мир, 1973 г. — стр. 162 - 164