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