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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Вгорі зліва — вершинно-критичний граф з хроматичним числом 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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 161–195. — DOI:10.1112/plms/s3-7.1.161.
  • T. Gallai. Kritische Graphen I // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (21 квітня). — С. 165–192.
  • T. Gallai. Kritische Graphen II // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 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) (21 квітня). — С. 117–134.
  • Ф. Харари. Теория графов. — 2-е. — М. : Едиториал УРСС, 2003. — ISBN 5-354-00301-6, ББК 22.144, 22.18, 22.19.
Отримано з https://uk.wikipedia.org/w/index.php?title=Критичний_граф&oldid=36140720