Число Хивуда

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

В 1890 году Хивуд доказал для всех поверхностей, , что кроме сферы не более

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

цвета необходимы для раскраски любого графа, встроенного в поверхность эйлеровой характеристики. $e(S)$ , или род $g(S)$ для ориентируемой поверхности. ^[1] Число $H(S)$ стал известен как число Хивуда в 1976 году.

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

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

Случай сферы — это гипотеза четырех цветов , которая была решена Кеннетом Аппелем и Вольфгангом Хакеном в 1976 году. ^[4]^[5]

Примечания

Бела Боллобас , Теория графов: вводный курс , Тексты для аспирантов по математике, том 63, Springer-Verlag, 1979. Збл 0411.05032 .
Томас Л. Саати и Пол Честер Кайнен ; Проблема четырех цветов: нападения и завоевания , Дувр, 1986 г. Збл 0463.05041 .

В эту статью включены материалы из номера Хивуда на PlanetMath , который распространяется по лицензии Creative Commons Attribution/Share-Alike License .

Ссылки

^ П. Дж. Хивуд (1890), «Теоремы о раскраске карт», Quarterly J. Math. , 24 : 322–339
^ П. Франклин (1934), «Задача шести цветов», Журнал математики и физики , 13 (1–4): 363–379, doi : 10.1002/sapm1934131363
^ Герхард Рингель; JWT Youngs (1968), «Решение проблемы раскраски карт Хивуда», Proceedings of the National Academy of Sciences , 60 (2): 438–445, Bibcode : 1968PNAS...60..438R , doi : 10.1073/pnas .60.2.438 , ISSN 0027-8424 , PMC 225066 , PMID 16591648
^ Кеннет Аппель; Вольфганг Хакен (1977), «Каждая плоская карта раскрашивается в четыре цвета. I. Разрядка» , Illinois Journal of Mathematics , 21 (3): 429–490, MR 0543792
^ Кеннет Аппель; Вольфганг Хакен; Джон Кох (1977), «Каждая плоская карта раскрашивается в четыре цвета. II. Сводимость» , Illinois Journal of Mathematics , 21 (3): 491–567, doi : 10.1215/ijm/1256049012 , MR 0543793

[1] П. Дж. Хивуд (1890), «Теоремы о раскраске карт», Quarterly J. Math. , 24 : 322–339

[2] П. Франклин (1934), «Задача шести цветов», Журнал математики и физики , 13 (1–4): 363–379, doi : 10.1002/sapm1934131363

[3] Герхард Рингель; JWT Youngs (1968), «Решение проблемы раскраски карт Хивуда», Proceedings of the National Academy of Sciences , 60 (2): 438–445, Bibcode : 1968PNAS...60..438R , doi : 10.1073/pnas .60.2.438 , ISSN 0027-8424 , PMC 225066 , PMID 16591648

[4] Кеннет Аппель; Вольфганг Хакен (1977), «Каждая плоская карта раскрашивается в четыре цвета. I. Разрядка» , Illinois Journal of Mathematics , 21 (3): 429–490, MR 0543792

[5] Кеннет Аппель; Вольфганг Хакен; Джон Кох (1977), «Каждая плоская карта раскрашивается в четыре цвета. II. Сводимость» , Illinois Journal of Mathematics , 21 (3): 491–567, doi : 10.1215/ijm/1256049012 , MR 0543793

[1]

[2]

[3]

[4]

[5]