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

Гипотеза Хивуда, или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, .... A000934,.

Гипотеза была сформулирована в 1890 году Перси Джоном Хивудом и доказана в 1968 Герхардом Рингелем и Тедом Янгсом. Один случай, а именно, неориентированная Бутылка Клейна, является исключением в общей формуле. Совершенно другой подход был нужен для куда более старой задачи нахождения числа цветов, необходимых для плоскости или сферы, и решённой в 1976 Вольфгангом Хакеном и Кеннетом Аппелем (теорема о четырёх красках). На сфере нижнюю границу найти легко, а на поверхностях более высокого рода легко установить верхнюю границу и она была доказана в оригинальной короткой статье Хивуда, содержащей формулировку гипотезы. Другими словами, для доказательства теоремы Рингель, Янгс и другие должны были сконструировать экстремальные примеры для каждого рода поверхности g = 1,2,3,.... Если g = 12s + k, род поверхности распадается на 12 случаев согласно остатку k = 0,1,2,3,4,5,6,7,8,9,10,11. Годы, в которые были решены двенадцать случаев и кто их решил:

• 1954, Рингель: случай 5
• 1961, Рингель: случаи 3,7,10
• 1963, Терри, Велч, Янгс: случаи 0,4
• 1964, Густин, Янгс: случай 1
• 1965, Густин: случай 9
• 1966, Янгс: случай 6
• 1967, Рингель, Янгс: случаи 2,8,11

Последние семь отдельных исключений были решены:

• 1967, Майер: случаи 18, 20, 23
• 1968, Рингель, Янгс: случаи 30, 35, 47, 59 и гипотеза была доказана.

Формальное утверждение

Граф Франклина.

Перси Джон Хивуд в 1890 году высказал гипотезу, что для заданного рода g > 0 минимальное число цветов, нужных для раскраски любого нарисованного на ориентируемой поверхности этого рода (или, эквивалентно, для раскраски любого разбиения поверхности на односвязные области), задаётся формулой

$\gamma (g)=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor ,$

где $\left\lfloor x\right\rfloor$ — функция «пол».

Сам Хивуд считал, что он доказал равенство в формуле, но уже через год Хеффтер указал неточности в доказательстве Хивуда, так что осталось неравенство. Сам Хеффтер доказал равенство для $0<g\leq 6$. В итоге утверждение о том, что в формуле Хивуда выполняется равенство, стало называться гипотезой Хивуда о раскраске карт

Заменяя род эйлеровой характеристикой, мы получим формулу, которая покрывает как ориентируемые, так и неориентируемые случаи,

$\gamma (\chi )=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor .$

Как показали Рингель и Янгс, это равенство выполняется для всех поверхностей, за исключением бутылки Клейна. Филип Франклин в 1930 году доказал, что для бутылки Клейна нужно максимум 6 цветов, а не 7, как гласит формула. Граф Франклина можно нарисовать на бутылке Клейна таким образом, что образуется шесть попарно граничащих областей, что показывает, что граница точна.

Верхняя граница, доказанная в оригинальной статье Хивуда, основывается на алгоритме жадной раскраски. Манипулируя характеристикой Эйлера, можно показать, что любой граф, вложенный в данную поверхность, должен иметь по меньшей мере одну вершину со степенью, меньшей указанной граничной величины. Если удалить эту вершину и раскрасить оставшийся граф, малое число инцидентных удалённой вершине рёбер даёт возможность добавить вершину обратно и дать ей цвет, не увеличивая числа необходимых цветов. В обратном направлении доказательство сложнее, в нём показывается, что во всех случаях (за исключением бутылки Клейна) полный граф с числом вершин, равным данному числу цветов, может быть вложен в поверхность.

Пример

Разбиение тора на семь взаимно граничащих областей, требующих семи цветов для раскраски.

Для тора g = 1, так что χ = 0. Таким образом, как следует из формулы, любое разбиение тора на области может быть выкрашено в семь цветов. Рисунок показывает разбиение тора, в котором каждая из семи областей граничит с каждой другой областью. Это разбиение показывает, что граница в семь цветов для этого случая точна. Границы этого разбиения образуют вложение графа Хивуда в тор.

Литература

• P. Franklin. A six color problem // MIT Journal of Mathematics and Physics. — 1934. — Т. 13. — С. 363–379.
• P. J. Heawood. Map colour theorem // Quarterly Journal of Mathematics. — 1890. — Т. 24. — С. 332–338.

• G. Ringel, J. W. T. Youngs. Solution of the Heawood map-coloring problem // Proceedings of the National Academy of Sciences of the United States of America. — 1968. — Т. 60, вып. 2. — С. 438–445. — doi:10.1073/pnas.60.2.438.
• Г. Рингель, Дж. Янгс. Решение проблемы Хивуда о раскраске карт // Теория графов. Покрытия, укладки, турниры. Сборник переводов. — М.: «Мир», 1974. — С. 82-90.
• Г. Рингель, Дж. Янгс. Решение проблемы Хивуда о раскраске карт: случай 11 // Теория графов. Покрытия, укладки, турниры. Сборник переводов. — М.: «Мир», 1974. — С. 91-113.

• Ф. Харари. Теория графов. — М.: Едиториал УРСС, 2003. — ISBN 5-354-00301-6, ББЛ 22.144, 22.18, 22.19.
• L. Heffter. Über das Problem der Nachbargebiete // Ann. Math.. — 1891. — Вып. 38.

Ссылки

• Weisstein, Eric W. Heawood Conjecture (англ.) на сайте Wolfram MathWorld.