RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Института математики НАН Беларуси // Архив

Тр. Ин-та матем., 2016, том 24, номер 1, страницы 47–50 (Mi timb258)

Три-раскрашиваемость чистых детских рисунков снáрков и задача “Охота на сна́рка”

Т. Э. Кренкель, Т. А. Куликова

Московский технический университет связи и информатики

Аннотация: Теорема Тейта как следствие из теоремы о четырех красках утверждает, что планарные кубические графы являются три-раскрашиваемыми, т.е. все их ребра могут быть раскрашены в три цвета. Первым содержательным контрпримером к теореме Тейта стал нетривиальный кубический (тривалентный) граф Петерсена $P,$ который является минимальным и единственным с хроматическим индексом 4. Целочисленная последовательность OEIS А130315 описывает, по определению Мартина Гарднера, число снарков (с охватом $\ge5),$ т.е. нетривиальных кубических графов с числом вершин равным $2n.$ Высказывается гипотеза, что при переходе от категории снарков Snarks к категории чистых детских рисунков снарков SnarksPureDessins, получаемые двукрашенные в вершинах графы могут быть три-раскрашиваемы по полуребрам. Приведено вложение графа Петерсена $P$ в двойной тор $\Sigma_2.$ Приводится доказательство $RGB$ теоремы о циклическом двойном накрытии графа Петерсена–Белого $PB.$

УДК: 511.6+519.17

Поступила в редакцию: 14.01.2016



© МИАН, 2024