Число Хивуда
Число Хивуда поверхности — это определённая верхняя граница для максимального числа цветов, необходимых для раскраски любого графа, вложенного в поверхность. В 1890 году Хивуд доказал для всех поверхностей, за исключением сферы, что не более чем
цветов необходимо для раскраски любого графа, вложенного в поверхность с эйлеровой характеристикой Шаблон:Sfn. Случай сферы соответствует гипотезе о четырёх красках, которую доказали Шаблон:Не переведено 5 и Вольфганг Хакен в 1976 годуШаблон:SfnШаблон:Sfn. Число стало известно как число Хивуда в 1976 году.
Франклин доказал, что хроматическое число графа, вложенного в бутылку Кляйна, может достигать , но никогда его не превосходитШаблон:Sfn. Позднее было доказано в работах Герхарда Рингеля и Дж. У. Т. Янгса, что полный граф с вершинами можно вложить в поверхность , за исключением случая, когда является бутылкой КляйнаШаблон:Sfn. Это показывает, что граница Хивуда не может быть улучшена.
Например, полный граф с вершинами можно вложить в тор следующим образом:
