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

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

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

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

• $k$-критический граф — это критический граф с хроматическим числом k.
• Граф G с хроматическим числом k является вершинно k-критическим, если каждая из его вершин является критическим элементом .

Свойства

• Пусть G есть k-критический граф с n вершинами и m рёбрами. Тогда:
  • G имеет только одну компоненту.
  • G конечен (теорема де Брёйна — Эрдёша Шаблон:Sfn).
  • δ(G) ≥ k − 1, то есть любая вершина смежна по меньшей мере k − 1 другим вершинам. Более строго, G рёберно (k − 1)-связен Шаблон:Sfn.
  • Если граф G (k − 1)-регулярен (каждая вершина смежна в точности k − 1 другим), то граф G либо является полным графом K_k, либо нечётным циклом. (Это теорема БруксаШаблон:Sfn).
  • 2 m ≥ (k − 1) n + k − 3 Шаблон:Sfn.
  • 2 m ≥ (k − 1) n + [(k − 3)/(k² − 3)] n Шаблон:Sfn.
  • Либо G может быть разбит на два меньших критических графа с ребром между каждой парой вершин, где две вершины берутся из разных частей, либо граф G имеет по меньшей мере 2k — 1 вершинШаблон:Sfn. Более строго, либо G имеет разложения такого типа, либо для каждой вершины v графа G существует k-раскраска, в которой v является единственной вершиной со своим цветом, а все остальные классы цветов имеют по меньшей мере две вершиныШаблон:Sfn.

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

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

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

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

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

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

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

См. также

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

Литература

• Шаблон:Статья
• Шаблон:Статья. (Indag. Math. 13.)
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга