Число Хивуда

Число Хивуда поверхности — это определённая верхняя граница для максимального числа цветов, необходимых для раскраски любого графа, вложенного в поверхность. В 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}$ вершинами можно вложить в тор следующим образом:

Примечания

1. Heawood, 1890, с. 322–339.
2. Appel, Haken, 1977, с. 429–490.
3. Appel, Haken, Koch, 1977, с. 491–567.
4. Franklin, 1934, с. 363–379.
5. Ringel, Youngs, 1968, с. 438–445.

Литература

• 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.