Тотальне розфарбування

Тотальне розфарбування в теорії графів — це спосіб розфарбування вершин і ребер графа. В загальному випадку, якщо не сказано іншого, забарвлення завжди вважається правильним в тому сенсі, що немає суміжних ребер та вершин на кінцях ребер, які розфарбовані в один і той же колір. Тотальне хроматичне число χ″(G) графа G — це найменше число кольорів, необхідних для тотального розфарбування G.

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

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

1. множина вершин графа T відповідає вершинам і ребрам графа G;
2. дві вершини T суміжні тоді і тільки тоді, коли відповідні елементи в G або суміжні, або інцидентні.

При такому визначенні тотальне розфарбування стає (правильним) вершинним розфарбуванням тотального графа.

Деякі властивості χ″(G):

1. χ″(G) ≥ Δ(G) + 1.
2. χ″(G) ≤ Δ(G) + 10²⁶. (Molloy, Reed, 1998)
3. χ″(G) ≤ Δ(G) + 8 ln⁸(Δ(G)) для досить великого Δ(G). (Hind, Molloy, Reed, 1998)
4. χ″(G) ≤ ch′(G) + 2.

Δ(G) — це максимальний степінь, а ch′(G) — індекс замовленого розфарбування ребер.

Тотальне розфарбування виникає природним шляхом, оскільки це просто суміш розфарбування вершин і ребер. Наступний крок — це розгляд верхніх меж тотального хроматичного числа в термінах максимальної степені за аналогією теорем Брукса або Візінга. Виявилося, що визначення верхніх меж тотальної розмальовки як функції від максимального степеня є складним завданням, яке залишається нерозв'язаним понад 40 років. Найбільш відома здогадка має такий вигляд.

Гіпотеза про тотальну розмальовку. (Бехзад, Візинг)

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

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

Відомо, що гіпотеза справедлива для декількох важливих класів графів, таких як двочасткові графи і більшість планарних графів, за винятком графів з максимальним степенем 6. Випадок планарних графів буде розв'язано, якщо буде доведено, що гіпотеза Візінга про планарні графи правильна. Також, якщо гіпотеза запропонованої розмальовки ребер справедлива, то χ″(G) ≤ Δ(G) + 3.

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

Існує зв'язок між реберним графом і тотальним графом: T(G) є ейлеровим тоді і тільки тоді, коли L(G) ейлерів.

Див. також

• Повне розфарбування

Посилання

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