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