Число Хивуда

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

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

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

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

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

Литература

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