Хроматичний індекс

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Проблема реберного розфарбування полягає в тому, щоб виявити чи можливо розфарбовати даний граф використовуючи не більше n кольорів. Мінімально потрібна кількість кольорів для розфарбовання даного графа називається хроматичний індекс. Наприклад, граф праворуч може бути розмальований трьома кольорами, але не може бути розмальованим двома кольорами, таким чином його хроматичний індекс три.

Визначення[ред.ред. код]

В подальшому, кажучи реберне розфарбовання графа без додаткових зауважень, ми маємо на увазі правильне розфарбовання ребер, яке заперечує існування двох суміжних ребер одного кольору. Правильне розфарбовання з використанням k кольорів — (правильне) реберне k-розфарбовання і є еквівалентом проблеми множини ребер на k підмножин. A реберне 3-розфарбовання кубічного графа іноді називають розфарбованням Тейта.

Найменша кількість кольорів необхідна для реберного розфарбовання графа G називається хроматичним індексом, або реберним хроматичним числом, χ′(G), також іноді \chi_1(G). Граф є ребрево k-хроматичним якщо його хроматичний індекс дорівнює k. Не треба плутати хроматичний індекс із хроматичним числом χ(G).

Властивості[ред.ред. код]

В подальшому, хай Δ(G) позначає максимальну ступінь; і μ(G), складність (буде більше 1 тільки для мультиграфів). Деякі властивості χ′(G):

  1. χ′(G) = 1 тоді і тільки тоді, якщо G є незалежною множиною ребер.
  2. χ′(G) ≥ Δ(G).
  3. χ′(G) ≤ Δ(G) + 1. (Теорема Візінга, названа на честь Вадима Візінга який винайшов її в 1964, розділив всі графи на на 2 класи: Клас 1 графи із χ′(G) = Δ(G); Клас 2 графи із χ′(G) = Δ(G)+1).
  4. χ′(G) ≤ Δ(G) + μ(G), де G може бути мультиграфом.
  5. χ′(G) ≤ (3/2)Δ(G) для будь-якого мультиграфа Shannon (1949).
  6. χ′(G) = Δ(G) якщо G дводольний граф. # χ′(G) = Δ(G) якщо G простий, планарний та Δ(G) ≥ 7. (Vizing (1965) combined with Sanders & Zhao (2001))
  7. χ′(G) = Δ(G) для майже всіх графів Erdős & Wilson (1977).

Класифікація графів і знаходження їх хроматичного індексу[ред.ред. код]

Як ми можемо бачити з наведенного вище χ′(G) дорівнює або either Δ(G), або Δ(G) + 1. Коли χ′(G) = Δ(G), G належить Класу 1; інакше, Класу 2. Holyer (1981) довів, що визначення належності простого графа до кокретного класу NP-повна задача. Однак, можна спробувати дати часткову характеристику. Наприклад, Vizing (1965) показав, що простий, планарний граф знаходиться в Класі 1 якщо його максимальна ступінь не менше 8. І навпаки, він помітив, що для максимального ступеню 2, 3, 4, і 5, існують прості графи з Класу 2. Наприклад, якщо почати з правильного багатогранника і заміняти кожне ребро на шлях з двох суміжних ребер, отримаємо простий планарний граф класа2 із максимальним ступенем 3, 4, або 5. (Кожний цикл непарної кількості вершин є графом класу 2 з максимальним ступенем 2.) Візінг припустив наступні результати для двох випадків, які він не зміг розв'язати:

Всі прості, планарні графи з максимальним ступенем 6 або 7 належать класу 1 Vizing (1965).

Sanders & Zhao (2001) частково довели це припущення Візінга. Вони показали, що всі прості планарні графи з максимальним ступенем 7 належать класу 1. Таким чином нерозв'язаним залишився випадок для простого планарного графа з максимальним ступенем 6.

Див. також[ред.ред. код]

Хроматичне число

Примітки[ред.ред. код]

  • Erdős, Paul; Wilson, Robin J. (1977), «Note on the chromatic index of almost all graphs», Journal of Combinatorial Theory, Series B 23: 255–257, doi:10.1016/0095-8956(77)90039-9 .
  • Holyer, Ian (1981), «The NP-completeness of edge-coloring», SIAM Journal on Computing 10: 718–720, doi:10.1137/0210055 .
  • Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems, New York: Wiley-Interscience, ISBN 0-471-02865-7 .
  • Kőnig, D. (1916), «Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre», Mathematische Annalen 77: 453–465, doi:10.1007/BF01456961 .
  • Sanders, Daniel P.; Zhao, Yue (2001), «Planar graphs of maximum degree seven are class I», Journal of Combinatorial Theory, Series B 83 (2): 201–212, doi:10.1006/jctb.2001.2047 .
  • Shannon, Claude E. (1949), «A theorem on coloring the lines of a network», J. Math. Physics 28: 148–151 .
  • Vizing, V. G. (1964), «On an estimate of the chromatic class of a p-graph», Diskret. Analiz. 3: 25–30 .
  • Vizing, V. G. (1965), «Critical graphs with given chromatic class», Metody Diskret. Analiz. 5: 9–17 .

Посилання[ред.ред. код]