Число Хевуда

Верхняя граница количества цветов, достаточного для раскраски любого графа

9-цветный тройной тор (поверхность рода 3) – пунктирные линии представляют ручки

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

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

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

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

Шестицветная бутылка Клейна — единственное исключение из гипотезы Хивуда

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

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

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

Примечания

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

В данной статье использованы материалы из номера Heawood на PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .

Ссылки

1. PJ Heawood (1890), «Теоремы о раскраске карт», Quarterly J. Math. , 24 : 322–339
2. П. Франклин (1934), «Проблема шести красок», Журнал математики и физики , 13 (1–4): 363–379, doi :10.1002/sapm1934131363
3. Герхард Рингель; Дж. У. Т. Янгс (1968), «Решение проблемы раскраски карт Хивуда», Труды Национальной академии наук , 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