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

В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа.Если не указано явно другое, тотальная раскраска предполагается правильной в том смысле, что никакие смежные вершины и никакие смежные рёбра и вершины, лежащие на концах рёбер, не раскрашиваются в один и тот же цвет. Тотальное хроматическое число χ″(G) графа G — это наименьшее число цветов, необходимых для тотальной раскраски G. Тотальным графом T = T(G) графа G называется граф, в котором 1. * множество вершин графа T соответствуют вершинам и рёбрам графа G; 2. * две вершины в T смежны тогда и только тогда, когда соответствующие элементы либо смежны в G, либо инцидентны. При таком определении тотальная раскраска становится (правильной) вершинной раскраской тотального графа. Несколько свойств χ″(G): 1. * χ″(G) ≥ Δ(G) + 1. 2. * χ″(G) ≤ Δ(G) + 1026. 3. * χ″(G) ≤ Δ(G) + 8 ln8(Δ(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) эйлеров.