Тотальная раскраска

В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа. Если не указано явно другое, тотальная раскраска предполагается правильной в том смысле, что никакие смежные вершины и никакие смежные рёбра и вершины, лежащие на концах рёбер, не раскрашиваются в один и тот же цвет.

Правильная тотальная раскраска клетки Фостера шестью цветами. Тотальное хроматическое число этого графа равно 6, поскольку степень каждой вершины равна 5 (5 смежных рёбер + 1 вершина = 6).

Тотальное хроматическое число χ″(G) графа G — это наименьшее число цветов, необходимых для тотальной раскраски G.

Тотальным графом T = T(G) графа G называется граф, в котором

1. множество вершин графа T соответствуют вершинам и рёбрам графа G;
2. две вершины в T смежны тогда и только тогда, когда соответствующие элементы либо смежны в G, либо инцидентны.

При таком определении тотальная раскраска становится (правильной) вершинной раскраской тотального графа.

Несколько свойств χ″(G):

1. χ″(G) ≥ Δ(G) + 1.
2. χ″(G) ≤ Δ(G) + 10²⁶.
3. χ″(G) ≤ Δ(G) + 8 ln⁸(Δ(G)) для достаточно большого Δ(G).
4. χ″(G) ≤ ch′(G) + 2.

Здесь Δ(G) — это максимальная степень, а ch′(G) — индекс предписанной раскраски рёбер.

Тотальная раскраска возникает естественным путём, поскольку она является простым смешением вершинной и рёберной раскрасок. Следующий шаг — это рассмотрение верхних границ тотального хроматического числа в терминах максимальной степени по аналогии с теоремами Брукса или Визинга. Оказалось, что определение верхних границ тотальной раскраски, как функции от максимальной степени, является сложной задачей и ускользает от математиков вот уже 40 лет.

Наиболее известная догадка выглядит так:

Гипотеза о тотальной раскраске.

χ″(G) ≤ Δ(G) + 2.

По всей видимости, термин «тотальная раскраска» и формулировку гипотезы независимо предложили Бехзад и Визинг в многочисленных публикациях между 1964 и 1968 годами (смотри книгу Йенсена и Тофта для деталей).

Известно, что гипотеза справедлива для нескольких важных классов графов, таких как двудольные графы и большинство планарных графов, за исключением графов с максимальной степенью 6. Случай планарных графов будет решён, если будет доказано, что гипотеза Визинга о планарных графах верна. Также, если гипотеза о предписанной раскраске рёбер справедлива, то χ″(G) ≤ Δ(G) + 3.

Были получены некоторые результаты относительно тотальной раскраски. Например, Килакос и Рид доказали, что дробный хроматический индекс тотального графа для графа G не превосходит Δ(G) + 2.

Упомянем также следующую связь рёберного графа и тотального графа:

T(G) является эйлеровым в том и только в том случае, когда L(G) эйлеров.

Литература

• Hugh Hind, Michael Molloy, Bruce Reed. Total coloring with Δ + poly(logΔ) colors // SIAM Journal on Computing. — 1998. — Т. 28, вып. 3. — С. 816—821. — doi:10.1137/S0097539795294578.
• Tommy R. Jensen, Bjarne Toft. Graph coloring problems. — New York: Wiley-Interscience, 1995. — ISBN 0-471-02865-7.
• Kyriakos Kilakos, Bruce Reed. Fractionally colouring total graphs // Combinatorica. — 1993. — Т. 13, вып. 4. — С. 435—440. — doi:10.1007/BF01303515.
• Michael Molloy, Bruce Reed. A bound on the total chromatic number // Combinatorica. — 1998. — Т. 18, вып. 2. — С. 241—280. — doi:10.1007/PL00009820.