"Записки научных семинаров ПОМИ"
Том 488, стр. 31-48
О правильных $3$-раскрасках ребер кубического графа
Д. В. Карпов
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург;
С.-Петербургский
государственный университет,
Университетский пр. 28,
Старый Петергоф,
198504 Санкт-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
В работе изучаются {\em определяющие} множества рёбер кубического графа (то есть, множества рёбер, 3-раскраска которых однозначно задает правильную 3-раскраску всех рёбер графа). В кубическом графе с $3n$ рёбрами доказано существование определяющего множества из $n$ рёбер. В трёхсвязном кубическом плоском графе с $3n$ рёбрами, каждая грань которого имеет не более чем $d$ вершин, доказано существование определяющего множества из не более чем $n - {n-2d+3\over 3d-8}$ ребер. В обоих случаях описан алгоритм построения определяющего множества.
Для связного кубического графа с $3n$ рёбрами строится такая серия многочленов над $\mathbb F_3$ от $ n+1$ переменных, что отличие от тождественного 0 любого из них эквивалентно наличию правильной 3-раскраски рёбер.
В заключение статьи доказывается, что связный кубический мультиграф $G$ на $2n$ вершинах имеет не более чем $3\cdot 2^n$ правильных 3-раскрасок рёбер. Эта оценка -- точная. В случае, когда $G$ имеет не более чем одну пару кратных рёбер, доказано, что $G$ имеет не более чем $9\cdot 2^{n-2}$ правильных 3-раскрасок рёбер.
Библ. -- 6 назв.
- Ключевые слова: кубический граф, 3-раскраски рёбер
[cubic graph, 3-edge coloring]
Полный текст(.pdf)