Гипотеза Хивуда

Гипотеза Хивуда, или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, ....

A000934,.

Гипотеза была сформулирована в 1890-ом году Перси Джоном Хивудом и доказана в 1968 Герхардом Рингелем и Тедом Янгсом. Один случай, а именно, неориентированная Бутылка Клейна, является исключением в общей формуле. Совершенно другой подход был нужен для куда более старой задачи нахождения числа цветов, необходимых для плоскости или сферы, и решённой в 1976 Вольфгангом Хакеном и Кеннтеом Аппелем (теорема о четырёх красках). На сфере нижнюю границу найти легко, а на поверхностях более высокого рода легко установить верхнюю границу и она была доказана в оригинальной короткой статье Хивуда, содержащей формулировку гипотезы. Другими словами, для доказательства теоремы Рингель, Янгс и другие должны были сконструировать экстремальные примеры для каждого рода поверхности g = 1,2,3,.... Если g = 12s + k, род поверхности распадается на 12 случаев согласно остатку k = 0,1,2,3,4,5,6,7,8,9,10,11. Годы, в которые были решены двенадцать случаев и кто их решил:

  • 1954, Рингель: случай 5
  • 1961, Рингель: случаи 3,7,10

1963, Терри, Велч, Янгс: случаи 0,4

  • 1964, Густин, Янгс: случай 1
  • 1965, Густин: случай 9
  • 1966, Янгс: случай 6

1967, Рингель, Янгс: случаи 2,8,11Последние семь отдельных исключений были решены:

  • 1967, Майер: случаи 18, 20, 23
  • 1968, Рингель, Янгс: случаи 30, 35, 47, 59 и гипотеза была доказана.

Источник: Википедия

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я