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

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

Правильная тотальная раскраска клетки Фостера шестью цветами. Тотальное хроматическое число этого графа равно 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²⁶[1].
3. χ″(G) ≤ Δ(G) + 8 ln⁸(Δ(G)) для достаточно большого Δ(G)[2].
4. χ″(G) ≤ ch′(G) + 2.

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

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

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

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

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

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

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

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

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

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