Розфарбовування ребер

Вперше поняття було застосовано відносно планарних графів. В процесі розфарбовування округів Англії на карті, математик Френсіс Гатрі сформулював проблему чотирьох фарб, зазначивши, що чотирьох кольорів достатньо для розфарбування, в якому будь-які два суміжних регіони були різних кольорів. Його брат переповів проблему своєму вчителю математики, Ауґустусу де Моргану, котрий, в свою чергу, згадав про неї у листі до Вільяма Гамільтона в 1852 році. Артур Келі піднімав цю проблему на зустрічі Лондонського математичного товариства в 1878 році. У тому ж році Пітер Тейт першим запропонував вирішення цієї проблеми. Розфарбовування вершин первісного графу він звів до розфарбування ребер двоїстого графу і припустив, що задача завжди має рішення. У 1880 році Альфред Кемпе опублікував статтю, в якій стверджував, що йому вдалося вирішити проблему і на десятиліття проблема чотирьох кольорів вважалася вирішеною. За це досягнення Кемпе був обраний членом Лондонського Королівського товариства, а пізніше — президентом Лондонського математичного товариства.

У 1890 році Джон Хівуд знайшов помилку в доведенні Кемпе. У цій же статті він довів теорему п'яти фарб, показавши, що будь-яка плоска карта може бути розфарбована не більше, ніж п'ятьма кольорами. При цьому він опирався на ідеї Кемпе. У наступному столітті було розроблено велику кількість теорій намагаючись зменшити мінімальну кількість кольорів. Теорема чотирьох фарб була остаточно доведена в 1977 році вченими Кеннетом Аппелем і Вольфгангом Гакеном. Ідея доведення багато в чому опиралася на ідеї Гівуда і Кемпе, оминувши увагою більшість проміжних досліджень. Доведення теореми чотирьох кольорів є одним з перших, де був використаний комп'ютерний перебір.

У 1912 році Джордж Девід Біркгоф запропонував для вивчення проблем розфарбовування використовувати хроматичний многочлен, який пізніше було узагальнено многочленом Татта. Кемпе в 1879 році вже звертав увагу на загальний випадок, коли граф не є планарним. Багато результатів з узагальненнями розфарбування планарних графів на поверхні вищих порядків з'явилося на початку 20 століття.

У 1960 році Клод Берж, під впливом поняття нульової помилки ємності графу, представленого Клодом Шенноном, сформулював гіпотезу про досконалі графи. Вона залишалась непідтвердженою протягом 40 років, поки зрештою її не довели математики Марія Чудновська, Робертсон, Сеймур і Томас у 2002 році.

Розфарбовування графу як алгоритмічну проблему почали вивчати з 1970-х років: визначення хроматичного числа — одна з 21 NP-повних задач Карпа (1972). Приблизно в той же час були розроблені різноманітні алгоритми на базі пошуку з поверненням та рекурсивного видалення-стиснення Зикова. З 1981 року розфарбовування графу застосовується для розподілу регістрів у компіляторах.

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

Найменша кількість кольорів необхідна для реберного розфарбування графу G називається хроматичним індексом, або реберним хроматичним числом, χ′(G), також іноді ${\displaystyle \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..

• Доведення теореми Візінга
• Реберне розфарбування та хроматичний індекс
• Проблема чотирьох фарб
• Розфарбування п'ятьма фарбами