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

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

В теории графов полная раскраска — это разновидность раскраски вершин ребер и . графа При использовании без каких-либо уточнений полная раскраска всегда считается правильной в том смысле, что ни смежным ребрам, ни смежным вершинам, ни ребру, ни одной конечной вершине не присвоен один и тот же цвет. Полное хроматическое число χ″( G ) графа G — это наименьшее количество цветов, необходимых для любой полной раскраски G. графа

Полный граф T = T ( G ) графа G — это граф такой, что (i) множество вершин T соответствует вершинам и ребрам графа G и (ii) две вершины смежны в T тогда и только тогда, когда соответствующие им вершины элементы либо соседние, либо инцидентные G. в Тогда полная раскраска G становится (собственной) раскраской вершин T ( G ) . Тотальная раскраска — это разбиение вершин и ребер графа на полные независимые множества .

Некоторые неравенства для χ″( G ):

1. χ″( г ) ≥ Δ( г ) + 1.
2. χ″( г ) ≤ Δ( г ) + 10 ²⁶ . (Моллой, Рид, 1998)
3. χ″( G ) ≤ Δ( G ) + 8 ln ⁸ (∆( G )) для достаточно больших ∆( G ). (Хинд, Моллой, Рид, 1998 г.)
4. χ″( G ) ≤ ch′( G ) + 2.

Здесь Δ( G ) — максимальная степень ; и ch'( G ), возможность выбора ребра .

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

Версия полной раскраски верхней границы максимальной степени — сложная задача, которая ускользала от математиков в течение 50 лет. Тривиальная нижняя граница для χ″( G ) равна ∆( G ) + 1. Некоторые графы, такие как циклы длины $n\not \equiv 0{\bmod {3}}$ и полные двудольные графы вида $K_{n,n}$ нужно Δ( G ) + 2 цвета, но графа, требующего большего количества цветов, не найдено. Это приводит к предположению, что каждому графу нужно либо ∆( G ) + 1, либо ∆( G ) + 2 цвета, но не больше:

Гипотеза тотальной раскраски ( Бехзад , Визинг). $\chi ''(G)\leq \Delta (G)+2.$

По-видимому, термин «полная раскраска» и формулировка гипотезы о полной раскраске неоднократно независимо вводились Бехзадом и Визингом в период с 1964 по 1968 год (см. Йенсен и Тофт). Известно, что гипотеза верна для нескольких важных классов графов, таких как все двудольные графы и большинство плоских графов, за исключением графов с максимальной степенью 6. Планарный случай может быть завершен, если гипотеза Визинга о плоском графе верна. Кроме того, если гипотеза о раскраске списка верна, то $\chi ''(G)\leq \Delta (G)+3.$

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

Ссылки

• Хинд, Хью; Моллой, Майкл; Рид, Брюс (1998). «Полная раскраска цветами Δ + поли(log Δ)». SIAM Journal по вычислительной технике . 28 (3): 816–821. дои : 10.1137/S0097539795294578 .
• Дженсен, Томми Р.; Тофт, Бьярн (1995). Задача о раскраске графа . Нью-Йорк: Wiley-Interscience. ISBN   0-471-02865-7 .
• Килакос, Кириакос; Рид, Брюс (1993). «Дробная раскраска итоговых графов». Комбинаторика . 13 (4): 435–440. дои : 10.1007/BF01303515 . S2CID   31163141 .
• Моллой, Майкл; Рид, Брюс (1998). «Ограничение общего хроматического числа». Комбинаторика . 18 (2): 241–280. дои : 10.1007/PL00009820 . hdl : 1807/9465 . S2CID   9600550 .