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