Число Хивуда

Число Хивуда поверхности — это определённая верхняя граница для максимального числа цветов, необходимых для раскраски любого графа, вложенного в поверхность. В 1890 году Хивуд доказал для всех поверхностей, за исключением сферы, что не более чем

${\displaystyle H(S)=\left\lfloor {\frac {7+{\sqrt {49-24e(S)}}}{2}}\right\rfloor }$

цветов необходимо для раскраски любого графа, вложенного в поверхность с эйлеровой характеристикой ${\displaystyle e(S)}$[1]. Случай сферы соответствует гипотезе о четырёх красках, которую доказали Кеннет Аппель и Вольфганг Хакен в 1976 году[2][3]. Число ${\displaystyle H(S)}$ стало известно как число Хивуда в 1976 году.

Франклин доказал, что хроматическое число графа, вложенного в бутылку Кляйна, может достигать ${\displaystyle 6}$, но никогда его не превосходит[4]. Позднее было доказано в работах Герхарда Рингеля и Дж. У. Т. Янгса, что полный граф с ${\displaystyle H(S)}$ вершинами можно вложить в поверхность ${\displaystyle S}$, за исключением случая, когда ${\displaystyle S}$ является бутылкой Кляйна[5]. Это показывает, что граница Хивуда не может быть улучшена.

Например, полный граф с ${\displaystyle 7}$ вершинами можно вложить в тор следующим образом: