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

Тотальне розфарбування в теорії графів — це спосіб розфарбування вершин і ребер графу. В загальному випадку, якщо не сказано іншого, забарвлення завжди вважається правильним в тому сенсі, що немає суміжних ребер та вершин на кінцях ребер, які розфарбовані в один і той же колір. Тотальне хроматичне число χ″(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) + 1026. (Molloy, Reed, 1998)
  3. χ″(G) ≤ Δ(G) + 8 ln8(Δ(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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.