Полная окраска

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

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

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

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

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

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

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

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

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

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

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