Граф Киттелля (Ijgs Tnmmyllx)
Перейти к навигации
Перейти к поиску
| граф Киттелля | |
|---|---|
 | |
| Назван в честь | Ирвинга Киттелля |
| Вершин | 23 |
| Рёбер | 63 |
| Радиус | 3 |
| Диаметр | 4 |
| Обхват | 3 |
| Хроматическое число | 4 |
| Хроматический индекс | 7 |
| Свойства | планарный |
Граф Киттелля — планарный граф с 23 вершинами и 63 рёбрами. Его единственное планарное вложение имеет 42 треугольных грани[1]. Граф назван именем Ирвинга Киттелля, который использовал его в качестве контрпримера доказательству Альфреда Кемпе[англ.] теоремы о четырёх красках[2].
Другие, более простые, контрпримеры — более ранние: Граф Пуссена (1896), граф Эрреры (1921) и два более поздних минимальных контрпримера: граф Сойфера (1997) и граф Фрича[англ.] (1998), оба порядка 9.
Другие свойства
[править | править код]Кликовая ширина графа равна 8[3].
Примечания
[править | править код]- ↑ Weisstein, Eric W. Kittell Graph (англ.) на сайте Wolfram MathWorld.
- ↑ Kittell, 1935, с. 407—413.
- ↑ HEULE, SZEIDER, 2015, с. 00:19, Table III.
Литература
[править | править код]- 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.
- 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.
 | Для улучшения этой статьи желательно:
|