Interested Article - Критический граф

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

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

Связанные определения

$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 , либо нечётным циклом . (Это теорема Брукса ).
- 2 m ≥ ( k − 1) n + k − 3 .
- 2 m ≥ ( k − 1) n + [( k − 3)/( k ² − 3)] n .
- Либо G может быть разбит на два меньших критических графа с ребром между каждой парой вершин, где две вершины берутся из разных частей, либо граф G имеет по меньшей мере 2 k — 1 вершин . Более строго, либо G имеет разложения такого типа, либо для каждой вершины v графа G существует k -раскраска, в которой v является единственной вершиной со своим цветом, а все остальные классы цветов имеют по меньшей мере две вершины .

Граф G является вершинно критическим тогда и только тогда, когда для любой вершины v существует оптимальная подходящая раскраска, в которой вершина v одна представляет класс цвета.

1-критических графов не существует.
Единственный 2-критический граф — это K ₂ .
Все 3-критические графы исчерпываются простыми циклами нечётной длины .

Как показал Хаджос , любой k -критический граф может быть сформирован из полного графа K _k путём комбинации построения Хайоша с операцией отожествления двух несмежных вершин. Граф, образованный таким образом, всегда требует k цветов в любой правильной раскраске.

4-критический, но не рёберно-критический граф, поскольку $\chi (G-x)=4$

Хотя каждый рёберно-критический граф обязательно является критическим, обратное неверно. Например, граф представленный справа, является 4-критическим, но не рёберно-критическим .

Вариации и обобщения

Дважды критический граф — это связный граф, в котором удаление любой пары смежных вершин уменьшает хроматическое число на два. Одна из нерешённых задач — является ли K _k единственным дважды критическим k -хроматическим графом .

См. также

Фактор-критический граф

Примечания

Следует отметить, что не всегда под критическим графом понимается критический k -хроматический граф. В статье Визинга под критическим графом размерности k понимается граф, у которого размерность любой собственной части меньше k. Под размерностью графа при этом понимается минимальная размерность метрического пространства, в которое можно вложить граф так, что все смежные вершины окажутся на расстоянии 1. ( )
.
.
.
.
.
.
.
, с. 167.
.
, с. 168-169.
.

Литература

R. L. Brooks, W. T. Tutte. On colouring the nodes of a network // Proceedings of the Cambridge Philosophical Society. — 1941. — Т. 37 , вып. 02 . — С. 194–197 . — doi : .
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 . — С. 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 . — С. 161–195 . — doi : .
T. Gallai. Kritische Graphen I // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963a. — Т. 8 . — С. 165–192 .
T. Gallai. Kritische Graphen II // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963b. — Т. 8 . — С. 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 . — С. 116–117 .
T. R. Jensen, B. Toft. . — 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 . — С. 189–194 . — doi : .
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) . — С. 117–134 .
Ф. Харари. Теория графов. — 2-е. — М. : Едиториал УРСС, 2003. — ISBN 5-354-00301-6 , ББК 22.144, 22.18, 22.19.