"Записки научных семинаров ПОМИ"
Том 497, стр. 26-52
Точная оценка на количество правильных 3-раскрасок рёбер связного кубического графа
М. П. Иванов
ФМКН СПбГУ,
14-я лин. B.O. 29Б,
Санкт-Петербург 199178, Россия
ivanovmihail99@gmail.com
- Аннотация:
В работе исследуется вопрос о верхней оценке количества правильных раскрасок
в три цвета рёбер у связного $2n$-вершинного графа, степени всех вершин которого равны
трём. Для этого был развит метод Карпова, с помощью которого им ранее была
получена более слабая версия оценки. Доказана оценка $2^n+8$ для чётных $n$ и
$2^n+4$ для нечётных $n$, а также найден единственный соответствующий ей пример;
таким образом, в этой задаче найдена и доказана точная верхняя оценка.
Библ. -- 2 назв.
- Ключевые слова: количество раскрасок, рёберные раскраски, кубические графы
[the number of colorings, edge colorings, cubic graphs ]
Полный текст(.pdf)