В математике , то работа Хивуд число из поверхности представляет собой верхнюю границу для числа цветов , которые достаточно , чтобы цвет любого графика встроенного в поверхности.
В 1890 году работа Хивуд доказана для всех поверхностей , кроме в области , что не более
цвета необходимы, чтобы раскрасить любой граф, вложенный в поверхность с эйлеровой характеристикой. , или род для ориентируемой поверхности. [1] Число стал известен как число Хивуда в 1976 году.
Франклин доказал, что хроматическое число графа, вложенного в бутылку Клейна, может достигать, но никогда не превышает . [2] Позже в работах Герхарда Рингеля , JWT Youngs и других авторов было доказано, что полный граф с вершины могут быть вложены в поверхность пока не это бутылка Клейна . [3] Таким образом установлено, что оценка Хивуда не может быть улучшена.
Например, полный график на вершины могут быть вложены в тор следующим образом:
Случай сферы - это гипотеза четырех цветов , которая была решена Кеннетом Аппелем и Вольфгангом Хакеном в 1976 году. [4] [5]
Заметки
- Бела Боллобас , Теория графов: вводный курс , Тексты для выпускников по математике, том 63, Springer-Verlag, 1979. Zbl 0411.05032 .
- Томас Л. Саати и Пол Честер Кайнен ; Проблема четырех цветов: нападения и завоевание , Дувр, 1986. Zbl 0463.05041 .
Эта статья включает материал из номера Heawood на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .
Рекомендации
- ^ PJ Heawood (1890), "Теоремы о раскраске карт", Quarterly J. Math. Oxford Ser. , 24 : 322–339
- ^ П. Франклин (1934), "Проблема шесть цветов", Журнал математики и физики , 13 (1-4): 363-379, DOI : 10.1002 / sapm1934131363
- ^ Герхард Рингель; JWT Янгс (1968), "Решение работе Хивуда Map-раскраска проблемы" , Труды Национальной академии наук , 60 (2): 438-445, 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), "Каждый Planar Карта Четыре Colorable II Приводимость.." , Штат Иллинойс Журнал математики , 21 (3): 491-567, DOI : 10,1215 / IJM / 1256049012 , MR 0543793