Число Хивуда

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

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

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

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

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

Литература

• Béla Bollobás. Graph Theory: An Introductory Course. — Springer-Verlag, 1979. — Т. volume 63. — (GTM). — ISBN 0-387-90399-2.
• Thomas L. Saaty, Paul Chester Kainen. The Four-Color Problem: Assaults and Conquest. — Dover, 1986.
• Heawood P. J. Map colouring theorems // Quarterly J. Math. Oxford Ser.. — 1890. — Т. 24.
• Kenneth Appel, Wolfgang Haken. Every Planar Map is Four Colorable. I. Discharging // Illinois Journal of Mathematics. — 1977. — Т. 21, вып. 3.
• Kenneth Appel, Wolfgang Haken, John Koch. Every Planar Map is Four Colorable. II. Reducibility // Illinois Journal of Mathematics. — 1977. — Т. 21, вып. 3.
• Franklin P. A Six Color Problem // Journal of Mathematics and Physics. — 1934. — Т. 13, вып. 1–4. — doi:10.1002/sapm1934131363.
• Gerhard Ringel, Youngs J. W. T. Solution of the Heawood Map-Coloring Problem // Proceedings of the National Academy of Sciences. — 1968. — Т. 60, № 2. — ISSN 0027-8424. — doi:10.1073/pnas.60.2.438.