Введение

Теорема об окрашивании графов на поверхностях

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

Пример

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