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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Вгорі зліва — вершинно-критичний граф з хроматичним числом 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 комбінацією побудови Хайоша[ru] з операцією ототожнення двох несуміжних вершин. Граф, утворений таким способом, завжди вимагає 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.