Граф Пуссена
| Граф Пуссена | |
|---|---|
 | |
| Вершины | 15 |
| Края | 39 |
| Радиус | 3 |
| Диаметр | 3 |
| Обхват | 3 |
| Автоморфизм | 2 ( З /2 З ) |
| Хроматическое число | 4 |
| Хроматический индекс | 6 |
| Характеристики | гамильтониан Планарный |
| Таблица графиков и параметров | |
В теории графов граф Пуссена представляет собой плоский граф с 15 вершинами и 39 ребрами. Он назван в честь Шарля Жана де ла Валле-Пуссена .
История
[ редактировать ]В 1879 году Альфред Кемпе опубликовал доказательство теоремы о четырёх цветах , одной из величайших гипотез в теории графов . [1] Хотя теорема верна, доказательство Кемпе неверно. Перси Джон Хивуд проиллюстрировал это в 1890 году. [2] с контрпримером, и де ла Валле-Пуссен пришел к такому же выводу в 1896 году с графом Пуссена . [3]
(Неверное) доказательство Кемпе основано на чередующихся цепочках , и поскольку эти цепочки оказываются полезными в теории графов, математики по-прежнему интересуются такими контрпримерами.Позже были найдены и другие: сначала граф Эрреры в 1921 году, [4] [5] затем граф Киттелла в 1935 году с 23 вершинами, [6] и, наконец, два минимальных контрпримера ( граф Сойфера в 1997 году и граф Фрича в 1998 году, оба порядка 9). [7] [8] [9]
Ссылки
[ редактировать ]- ^ Кемпе, AB «К географической проблеме четырех цветов». амер. Дж. Математика. 2, 193–200, 1879.
- ^ П. Дж. Хивуд, «Теорема о цвете карты», Quart. J. Pure Appl. Математика. 24 (1890), 332–338.
- ^ Р. А. Уилсон, Графы, раскраски и теорема о четырех цветах, Oxford University Press, Оксфорд, 2002. MR 1888337 Збл 1007.05002 .
- ^ Эррера, А. «О раскраске карт и некоторых вопросах анализа местности». Кандидатская диссертация. 1921.
- ^ Питер Хейниг. Доказательство того, что граф Эрреры представляет собой узкий тупик Кемпе . 2007.
- ^ Киттелл, И. «Группа операций на частично раскрашенной карте». Бык. амер. Математика. Соц. 41, 407–413, 1935.
- ^ А. Сойфер, «Раскраска карт в викторианскую эпоху: проблемы и история», Mathematics Competition 10 (1997), 20–31.
- ^ Р. Фрич и Г. Фрич, Теорема о четырех цветах, Springer, Нью-Йорк, 1998. MR 1633950 .
- ^ Гетнер, Э. и Спрингер, WM II. « Насколько ложно доказательство Кемпе теоремы о четырех цветах? » Конгр. Число. 164, 159–175, 2003.