Число Хивуда (Cnvlk }nfr;g)

Перейти к навигации Перейти к поиску

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

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

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

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

Примечания

[править | править код]
  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.