Гипотеза Хивуда
| Определение: |
| Хроматическим числом поверхности поверхности или -ым числом Хивуда называется число , равное максимальному хроматическому числу графа, который можно уложить на поверхность -ого рода. |
Содержание
Теорема о нижней границе хроматического числа поверхности
| Теорема (Теорема Рингеля и Янгса): |
Для любого положительного целого числа хроматическое число поверхности -ого рода . |
| Доказательство: |
|
Воспользуемся формулой Эйлера . Давайте докажем нижнюю границу на . Максимизируем число граней: каждая из них может быть треугольником. Тогда для существует неулучшаемая нижняя граница:
. Рассмотрим полный граф , тогда получаем, что , функция монотонно возрастает при , и для любого наибольшее значение функция достигается при . Поскольку , откуда получаем, что . |
Теорема о верхней границе хроматического числа поверхности
| Теорема (Гипотеза Хивуда): |
Для любого положительного целого числа хроматическое число поверхности -ого рода . |
| Доказательство: |
|
Пусть задан граф с вершина, рёбрами и гранями, также будем считать, что — триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности -ого рода). Обозначим за — среднюю степень вершины графа , тогда должно быть справедливым следующее равенство:
Воспользуемся формулой Эйлера , откуда и и подставляя в первое равенство получаем
Поскольку , то
Найдём единственный положительный корень неравенства
Обозначим за . Если , то тогда граф очевидно можно раскрасить в цветов и неравенство верное. Допустим, что , тогда Значит в такое графе существует хотя бы одна вершина степени не больше , стянем её с любой соседней и получим новый граф с вершинами. Если , то граф можно раскрасить в цветов, значит и сам граф можно также раскрасить в цветов, если , то опять найдём вершину степени и снова стянем её и будем продолжать так до тех пор, пока не получим желаемый граф. |
Из всего выше сказанного получаем, что в точности равно .
Проблема четырёх красок
Заметим, что теорема Хивуда не работает при , поэтому проблема четырёх красок не может быть доказана с помощью этой теоремы, однако при подстановке получаем .
См. также
Источники информации
- Wikipedia — Heawood conjecture
- Последовательность чисел Хивуда
- Ф.Харари «Теория графов» — М.: Мир, 1973 г. — стр. 162 - 164
