Число Хивуда - Heawood number

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

В 1890 году компания Heawood доказала свою пригодность для любых поверхностей. Кроме то сфера это не более чем

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

цвета необходимы для раскрашивания любого графа, встроенного в поверхность Эйлерова характеристика ${ Displaystyle е (S)}$ .^[1] Случай сферы - это четырехцветная гипотеза который был урегулирован Кеннет Аппель и Вольфганг Хакен в 1976 г.^[2]^[3] Номер ${ Displaystyle H (S)}$ стал известен как число Хивуда в 1976 году.

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

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

Примечания

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

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

Рекомендации

^ Хивуд, П. Дж. (1890), «Теоремы о раскраске карт», Ежеквартально J. Math. Oxford Ser., 24: 322–339
^ Аппель, Кеннет; Хакен, Вольфганг (1977), «Каждую планарную карту можно раскрасить в четыре цвета. I. Разрядка», Иллинойсский журнал математики, 21 (3): 429–490, Г-Н 0543792
^ Аппель, Кеннет; Хакен, Вольфганг; Кох, Джон (1977), «Каждую планарную карту можно раскрасить в четыре цвета. II. Сводимость», Иллинойсский журнал математики, 21 (3): 491–567, Дои:10.1215 / ijm / 1256049012, Г-Н 0543793
^ Франклин, П. (1934), «Шесть цветов», Журнал математики и физики, 13 (1–4): 363–379, Дои:10.1002 / sapm1934131363
^ Рингель, Герхард; Янгс, Дж. У. Т. (1968), «Решение проблемы раскраски карты Хивуда», Труды Национальной академии наук, 60 (2): 438–445, Дои:10.1073 / pnas.60.2.438, ISSN 0027-8424, ЧВК 225066, PMID 16591648

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

[2] Аппель, Кеннет; Хакен, Вольфганг (1977), «Каждую планарную карту можно раскрасить в четыре цвета. I. Разрядка», Иллинойсский журнал математики, 21 (3): 429–490, Г-Н 0543792

[3] Аппель, Кеннет; Хакен, Вольфганг; Кох, Джон (1977), «Каждую планарную карту можно раскрасить в четыре цвета. II. Сводимость», Иллинойсский журнал математики, 21 (3): 491–567, Дои:10.1215 / ijm / 1256049012, Г-Н 0543793

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

[5] Рингель, Герхард; Янгс, Дж. У. Т. (1968), «Решение проблемы раскраски карты Хивуда», Труды Национальной академии наук, 60 (2): 438–445, Дои:10.1073 / pnas.60.2.438, ISSN 0027-8424, ЧВК 225066, PMID 16591648

[1]

[2]

[3]

[4]

[5]