Граф Пуссена

граф Пуссена
Вершин 15
Рёбер 39
Радиус 3
Диаметр 3
Обхват 3
Автоморфизмы (Z/2Z)
Хроматическое число 4
Хроматический индекс 6
Свойства гамильтонов
планарный
Логотип Викисклада Медиафайлы на Викискладе
Переплетённые цепи Кемпе[англ.] в графе Пуссена. Границы областей на этом рисунке образуют граф Пуссена, частично раскрашенный в четыре цвета, внешняя область не раскрашена. Синие/жёлтые и синие/зелёные цепочки Кемпе (жёлтые и зелёные линии) соединяют соседей внешней области, так что согласно Кемпе придётся обменять цвета в левой красной/жёлтой цепочке и правой красной/зелёной цепочке (красные линии), чтобы позволить выкрасить внешнюю область в красный цвет. Так как синие–жёлтые и синие–зелёные цепочки пересекаются, эта перестановка цветов приведёт к тому, что верхняя жёлтая и зелёная области станут красными, что приведёт к неверной раскраске.

Граф Пуссена — это планарный граф с 15 вершинами и 39 рёбрами. Он назван именем Шарля Жана де Ла Валле-Пуссена.

История

В 1879 году Альфред Кемпе[англ.] опубликовал доказательство теоремы о четырёх красках, одной из великих гипотез в теории графов[1]. Хотя сама теорема верна, доказательство Кемпе ошибочно. Перси Джон Хивуд продемонстрировал это в 1890[2] контрпримером, а де Ла Валле-Пуссен пришёл к тому же заключению в 1896 году с графом Пуссена[3].

(Неверное) доказательство Кемпе основано на чередующихся цепях[англ.] и, поскольку это доказательство на основе цепей оказалось полезным в теории графов, математики продолжают интересоваться такими контрпримерами. Другие контрпримеры были найдены позже, это граф Эрреры в 1921[4][5], граф Киттелля в 1935 с 23 вершинами[6] и, наконец, два минимальных контрпримера (граф Сойфера в 1997 и граф Фрича[англ.] в 1998, оба порядка 9)[7][8][9].

Другие свойства

Кликовая ширина графа равна 7[10].

Примечания

  1. ↑ Kempe, 1879, с. 193–200.
  2. ↑ Heawood, 1890, с. 332–338.
  3. ↑ Wilson, 2002.
  4. ↑ Errera, 1921.
  5. ↑ Heinig, 2007.
  6. ↑ Kittell, 1935, с. 407–413.
  7. ↑ Soifer, 1997, с. 20–31.
  8. ↑ Fritsch, Fritsch, 1998.
  9. ↑ Gethner, Springer, 2003, с. 159–175.
  10. ↑ HEULE, SZEIDER, 2015, с. 00:19, Table III.

Литература

  • Kempe A. B. On the Geographical Problem of Four-Colors // Amer. J. Math.. — 1879. — Вып. 2.
  • Heawood P. J. Map colour theorem // Quart. J. Pure Appl. Math.. — 1890. — Вып. 24.
  • Wilson R. A. Graphs, colourings and the four-colour theorem. — Oxford: Oxford University Press, 2002.
  • Errera A. Du coloriage des cartes et de quelques questions d'analysis situs.. — 1921. — (Ph.D. thesis).
  • Peter Heinig. Proof that the Errera Graph is a narrow Kempe-Impasse. — 2007.
  • Kittell I. A Group of Operations on a Partially Colored Map // Bull. Amer. Math. Soc. — 1935. — Т. 41, вып. 6. — doi:10.1090/S0002-9904-1935-06104-X.
  • Soifer A. Map coloring in the victorian age: problems and history // Mathematics Competitions. — 1997. — Вып. 10.
  • Fritsch R., Fritsch G. The Four-Color Theorem. — New York: Springer, 1998.
  • Gethner E., Springer W. M. II. How False Is Kempe's Proof of the Four-Color Theorem? // Congr. Numer.. — 2003. — Вып. 164.
  • MARIJN J. H. HEULE, STEFAN SZEIDER. A SAT approach to clique-width. // ACM Transactions on Computational Logic. — 2015. — Вып. 0,0 (January 2015). — doi:10.1145/0000000.000000.

Ссылки