Критичний граф

Критичний граф — граф, у якому видалення будь-якої вершини або ребра призводить до зменшення хроматичного числа графу.

Вгорі зліва — вершинно-критичний граф з хроматичним числом 6. Решта N-1 подграфов мають хроматичне число 5.

Пов'язані визначення

• ${\displaystyle k}$-критичний граф — це критичний граф із хроматичним числом k.
• Граф G з хроматичним числом k є вершинно-k-критичним, якщо кожна з його вершин є критичним елементом.

Властивості

• Нехай G є k-критичним графом із n вершинами і m ребрами. Тоді:
  • G має тільки одну компоненту.
  • G — скінченний (теорема де Брёйна — Ердеша ).
  • δ(G) ≥ k − 1, тобто будь-яка вершина суміжна щонайменше k − 1 іншим вершинам. Строгіше, G реберно (k − 1)-зв'язний.
  • Якщо граф G (k − 1)-регулярний (кожна вершина суміжна рівно k − 1 іншим), то граф G або є повним графом K_k, або непарним циклом ((теорема Брукса)).
  • 2m ≥ (k − 1)n + k − 3.
  • 2m ≥ (k − 1)n + [(k − 3)/(k² − 3)]n.
  • Або G можна розбити на два менших критичних графи з ребром між кожною парою вершин, де дві вершини беруться з різних частин, або граф G має щонайменше 2k − 1 вершин. Строгіше, або G має розклад такого типу, або для кожної вершини v графу G існує k-розфарбування, в якому v є єдиною вершиною зі своїм кольором, а всі інші класи кольорів мають щонайменше дві вершини.

• Граф G є вершинно-критичним тоді і тільки тоді, коли для будь-якої вершини v існує оптимальне підхоже розфарбування, в якому вершина v одна представляє клас кольору.

• 1-критичних графів не існує.
• Єдиний 2-критичний граф — це K_2.
• Всі 3-критичні графи вичерпуються простими циклами непарної довжини.

• Як показав Хайош, будь-який k-критичний граф можна сформувати з повного графу K_k комбінацією ^[ru] з операцією ототожнення двох несуміжних вершин. Граф, утворений таким способом, завжди вимагає k кольорів у будь-якому правильному розфарбуванні.

4-критичний, але не реберно-критичний граф, оскільки ${\displaystyle \chi (G-x)=4}$

• Хоча кожен реберно-критичний граф обов'язково є критичним, зворотне хибне. Наприклад, граф наведений праворуч, є 4-критичним, але не реберно-критичним.

Варіації та узагальнення

• Двічі критичний граф — це зв'язний граф, у якому видалення будь-якої пари суміжних вершин зменшує хроматичне число на 2. Одна з нерозв'язаних задач — чи є K_k єдиним двічі критичним k-хроматичним графом.

Див. також

Примітки

1. Слід зазначити, що не завжди під критичним графом розуміють критичний k-хроматичний граф. У статті Візінга під критичним графом розмірності k розуміють граф, у якого розмірність будь-якої власної частини менша від k. Під розмірністю графа при цьому розуміють мінімальну розмірність метричного простору, в який можна вкласти граф так, що всі суміжні вершини опиняться на відстані 1. (Визинг, 1968)
2. de Bruijn, Erdős, 1951.
3. Lovász, 1992.
4. Brooks, Tutte, 1941.
5. Dirac, 1957.
6. Gallai, 1963a.
7. Gallai, 1963b.
8. Stehlík, 2003.
9. Харари, 2003, с. 167.
10. Hajós, 1961.
11. Харари, 2003, с. 168-169.
12. Erdős, 1966.

Література

• R. L. Brooks, W. T. Tutte. On colouring the nodes of a network // Proceedings of the Cambridge Philosophical Society. — 1941. — Т. 37, вип. 02 (17 червня). — С. 194–197. — DOI:10.1017/S030500410002168X.
• N. G. de Bruijn, P. Erdős. A colour problem for infinite graphs and a problem in the theory of relations // Nederl. Akad. Wetensch. Proc. Ser. A. — 1951. — Т. 54 (17 червня). — С. 371–373.. ( 13.)
• G. A. Dirac. A theorem of R. L. Brooks and a conjecture of H. Hadwiger // Proceedings of the London Mathematical Society. — 1957. — Т. 7, вип. 1 (17 червня). — С. 161–195. — DOI:10.1112/plms/s3-7.1.161.
• T. Gallai. Kritische Graphen I // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (17 червня). — С. 165–192.
• T. Gallai. Kritische Graphen II // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (17 червня). — С. 373–395..
• . Über eine Konstruktion nicht n-färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — Т. 10 (17 червня). — С. 116–117.
• T. R. Jensen, B. Toft. Graph coloring problems. — New York : Wiley-Interscience, 1995. — .
• Matěj Stehlík. Critical graphs with connected complements // . — 2003. — Т. 89, вип. 2 (17 червня). — С. 189–194. — (Series B). — DOI:10.1016/S0095-8956(03)00069-8.
• László Lovász. Combinatorial Problems and Exercises (Second Edition). — North-Holland, 1992.
• Paul Erdős. In Theory of Graphs. — Proc. Colloq., Tihany, 1966. — С. 361.
• В. Г. Визинг. Некоторые нерешенные задачи в теории графов // Успехи Математических Наук. — 1968. — Т. XXIII, вип. 6 (144) (17 червня). — С. 117–134.
• Ф. Харари. Теория графов. — 2-е. — М. : Едиториал УРСС, 2003. — , ББК 22.144, 22.18, 22.19.