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

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

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

Пов'язані визначення
  • -критичний граф — це критичний граф із хроматичним числом k.
  • Граф G з хроматичним числом k є вершинно-k-критичним, якщо кожна з його вершин є критичним елементом[1].

Властивості
  • Нехай G є k-критичним графом із n вершинами і m ребрами. Тоді:
    • G має тільки одну компоненту.
    • G — скінченний (теорема де Брёйна — Ердеша [2]).
    • δ(G) ≥ k − 1, тобто будь-яка вершина суміжна щонайменше k − 1 іншим вершинам. Строгіше, G реберно (k − 1)-зв'язний[3].
    • Якщо граф G (k − 1)-регулярний (кожна вершина суміжна рівно k − 1 іншим), то граф G або є повним графом Kk, або непарним циклом (теорема Брукса[4]).
    • 2m ≥ (k − 1)n + k − 3[5].
    • 2m ≥ (k − 1)n + [(k − 3)/(k2 − 3)]n[6].
    • Або G можна розбити на два менших критичних графи з ребром між кожною парою вершин, де дві вершини беруться з різних частин, або граф G має щонайменше 2k − 1 вершин[7]. Строгіше, або G має розклад такого типу, або для кожної вершини v графу G існує k-розфарбування, в якому v є єдиною вершиною зі своїм кольором, а всі інші класи кольорів мають щонайменше дві вершини[8].
  • Граф G є вершинно-критичним тоді і тільки тоді, коли для будь-якої вершини v існує оптимальне підхоже розфарбування, в якому вершина v одна представляє клас кольору.
  • 1-критичних графів не існує.
  • Єдиний 2-критичний граф — це K2.
  • Всі 3-критичні графи вичерпуються простими циклами непарної довжини[9].
  • Як показав Хаджос[10], будь-який k-критичний граф можна сформувати з повного графу Kk комбінацією побудови Гайоша з операцією ототожнення двох несуміжних вершин. Граф, утворений таким способом, завжди вимагає k кольорів у будь-якому правильному розфарбуванні.
4-критичний, але не реберно-критичний граф, оскільки
  • Хоча кожен реберно-критичний граф обов'язково є критичним, зворотне хибне. Наприклад, граф наведений праворуч, є 4-критичним, але не реберно-критичним[11].

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

Див. також
  • Фактор-критичний граф

Примітки
  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 (27 лютого). — С. 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 (27 лютого). — С. 371–373.. (Indag. Math. 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 (27 лютого). — С. 161–195. — DOI:10.1112/plms/s3-7.1.161.
  • T. Gallai. Kritische Graphen I // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (27 лютого). — С. 165–192.
  • T. Gallai. Kritische Graphen II // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (27 лютого). — С. 373–395..
  • G. Hajós. Über eine Konstruktion nicht n-färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — Т. 10 (27 лютого). — С. 116–117.
  • T. R. Jensen, B. Toft. Graph coloring problems. — New York : Wiley-Interscience, 1995. — ISBN 0-471-02865-7.
  • Matěj Stehlík. Critical graphs with connected complements // Journal of Combinatorial Theory. — 2003. — Т. 89, вип. 2 (27 лютого). — С. 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) (27 лютого). — С. 117–134.
  • Ф. Харари. Теория графов. — 2-е. — М. : Едиториал УРСС, 2003. — ISBN 5-354-00301-6, ББК 22.144, 22.18, 22.19.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.