Критический граф — граф, в котором удаление любой вершины или ребра приводит к уменьшению хроматического числа графа.
Связанные определения
-критический граф — это критический граф с хроматическим числом k. Граф G с хроматическим числом k является вершинно k-критическим, если каждая из его вершин является критическим элементом Следует отметить, что не всегда под критическим графом понимается критический k-хроматический граф. В статье Визинга под критическим графом размерности k понимается граф, у которого размерность любой собственной части меньше k. Под размерностью графа при этом понимается минимальная размерность метрического пространства, в которое можно вложить граф так, что все смежные вершины окажутся на расстоянии 1. .
Свойства Пусть G есть k-критический граф с n вершинами и m рёбрами. Тогда: G имеет только одну компоненту. G конечен (теорема де Брёйна — Эрдёша ). δ(G) ≥ k − 1, то есть любая вершина смежна по меньшей мере k − 1 другим вершинам. Более строго, G рёберно (k − 1)-связен . Если граф G (k − 1)-регулярен (каждая вершина смежна в точности k − 1 другим), то граф G либо является полным графом Kk, либо нечётным циклом. (Это теорема Брукса). 2 m ≥ (k − 1) n + k − 3 . 2 m ≥ (k − 1) n + [(k − 3)/(k2 − 3)] n . Либо G может быть разбит на два меньших критических графа с ребром между каждой парой вершин, где две вершины берутся из разных частей, либо граф G имеет по меньшей мере 2k — 1 вершин. Более строго, либо G имеет разложения такого типа, либо для каждой вершины v графа G существует k-раскраска, в которой v является единственной вершиной со своим цветом, а все остальные классы цветов имеют по меньшей мере две вершины.
Граф G является вершинно критическим тогда и только тогда, когда для любой вершины v существует оптимальная подходящая раскраска, в которой вершина v одна представляет класс цвета.
1-критических графов не существует. Единственный 2-критический граф — это K2. Все 3-критические графы исчерпываются простыми циклами нечётной длины.
Как показал Хаджос, любой k-критический граф может быть сформирован из полного графа Kk путём комбинации построения Хайоша с операцией отожествления двух несмежных вершин. Граф, образованный таким образом, всегда требует k цветов в любой правильной раскраске.
Хотя каждый рёберно-критический граф обязательно является критическим, обратное неверно. Например, граф представленный справа, является 4-критическим, но не рёберно-критическим.
Вариации и обобщения Дважды критический граф — это связный граф, в котором удаление любой пары смежных вершин уменьшает хроматическое число на два. Одна из нерешённых задач — является ли Kk единственным дважды критическим k-хроматическим графом.
См. также Фактор-критический граф
Примечания
Литература
. (Indag. Math. 13.)
.
Категория:Семейства графов Категория:Раскраска графа