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

В теории графов критическим графом называется неориентированный граф, все собственные подграфы которого имеют меньшее хроматическое число . В таком графе каждая вершина или ребро является критическим элементом в том смысле, что ее удаление уменьшит количество цветов, необходимых для раскраски данного графа. Уменьшение количества цветов не может быть более чем на один.

Вариации

А $k$ -критический граф – критический граф с хроматическим числом $k$ . График $G$ с хроматическим номером $k$ является $k$ -vertex-critical , если каждая его вершина является критическим элементом. Критические графы — это минимальные члены с точки зрения хроматического числа, которое является очень важной мерой в теории графов.

Некоторые свойства А. $k$ -критический граф $G$ с $n$ вершины и $m$ края:

$G$ имеет только один компонент .
$G$ конечен (это теорема де Брейна–Эрдёша ). ^[1]
Минимальная степень $\delta (G)$ подчиняется неравенству $\delta (G)\geq k-1$ . То есть каждая вершина смежна хотя бы с $k-1$ другие. Сильнее, $G$ является $(k-1)$ - с краевым соединением . ^[2]
Если $G$ является регулярным графом степени $k-1$ , что означает, что каждая вершина смежна ровно с $k-1$ другие, тогда $G$ либо полный граф $K_{k}$ с $n=k$ нечетной длины вершины или граф циклов . Это теорема Брукса . ^[3]
$2m\geq (k-1)n+k-3$ . ^[4]
$2m\geq (k-1)n+\lfloor (k-3)/(k^{2}-3)\rfloor n$ . ^[5]
Или $G$ может быть разложен на два меньших критических графа с ребром между каждой парой вершин, включающим по одной вершине из каждого из двух подграфов, или $G$ имеет по крайней мере $2k-1$ вершины. ^[6] Более сильно, либо $G$ имеет разложение этого типа, или для каждой вершины $v$ из $G$ есть $k$ -раскраска, в которой $v$ является единственной вершиной своего цвета, а каждый другой цветовой класс имеет как минимум две вершины. ^[7]

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

Как показал Хайос (1961) , каждый $k$ -критический граф может быть сформирован из полного графа $K_{k}$ путем объединения конструкции Хайоса с операцией, идентифицирующей две несмежные вершины. Графики, построенные таким образом, всегда требуют $k$ цвета в любой подходящей расцветке. ^[8]

Дважды критический граф — это связный граф, в котором удаление любой пары соседних вершин уменьшает хроматическое число на два. Открытой проблемой является определение того, является ли $K_{k}$ является единственным дважды критическим $k$ -хроматический граф. ^[9]

См. также

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

Ссылки

^ де Брёйн, Нью-Йорк ; Эрдеш, П. (1951), «Проблема цвета бесконечных графов и проблема теории отношений» , Недерл. Акад. Ветенш. Учеб. Сер. A , 54 : 371–373, CiteSeerX 10.1.1.210.6623 , doi : 10.1016/S1385-7258(51)50053-7 . ( Индаг. Матем. 13. )
^ Ловас, Ласло (1992), «Решение к упражнению 9.21», Комбинаторные задачи и упражнения (2-е изд.), Северная Голландия, ISBN 978-0-8218-6947-5
^ Брукс, Р.Л. (1941), «О раскраске узлов сети», Труды Кембриджского философского общества , 37 (2): 194–197, Бибкод : 1941PCPS...37..194B , doi : 10.1017/S030500410002168X , S2CID 209835194
^ Дирак, Джорджия (1957), «Теорема Р. Л. Брукса и гипотеза Х. Хадвигера», Труды Лондонского математического общества , 7 (1): 161–195, doi : 10.1112/plms/s3-7.1.161
^ Галлай, Т. (1963), «Критище Графен I», Опубл. Математика. Инст. Венгрия. акад. наук. , 8 : 165–192
^ Галлай, Т. (1963), «Критище Графен II», Опубл. Математика. Инст. Венгрия. акад. наук. , 8 : 373–395
^ Стелик, Матей (2003), «Критические графы со связными дополнениями», Журнал комбинаторной теории , серия B, 89 (2): 189–194, doi : 10.1016/S0095-8956(03)00069-8 , MR 2017723
^ Хайос, Г. (1961), «О конструкции не $-n-$ раскрашиваемых графов», Wiss. З. Мартина Лютера Univ. Галле-Виттенберг Математика-Природа. Серия , 10 : 116–117
^ Эрдеш, Пол (1967), «Проблема 2», Теория графов , Proc. Коллок., Тихань, с. 361

Дальнейшее чтение

Дженсен, ТР; Тофт, Б. (1995), Проблемы раскраски графов , Нью-Йорк: Wiley-Interscience, ISBN. 0-471-02865-7
Штибиц, Майкл; Туза, Жолт; Фойгт, Маргит (6 августа 2009 г.), «В списке критических графов», Discrete Mathematics , 309 (15), Elsevier: 4931–4941, doi : 10.1016/j.disc.2008.05.021

[dbe-1] де Брёйн, Нью-Йорк ; Эрдеш, П. (1951), «Проблема цвета бесконечных графов и проблема теории отношений» , Недерл. Акад. Ветенш. Учеб. Сер. A , 54 : 371–373, CiteSeerX 10.1.1.210.6623 , doi : 10.1016/S1385-7258(51)50053-7 . ( Индаг. Матем. 13. )

[lovasz-2] Ловас, Ласло (1992), «Решение к упражнению 9.21», Комбинаторные задачи и упражнения (2-е изд.), Северная Голландия, ISBN 978-0-8218-6947-5

[brooks-3] Брукс, Р.Л. (1941), «О раскраске узлов сети», Труды Кембриджского философского общества , 37 (2): 194–197, Бибкод : 1941PCPS...37..194B , doi : 10.1017/S030500410002168X , S2CID 209835194

[dirac-4] Дирак, Джорджия (1957), «Теорема Р. Л. Брукса и гипотеза Х. Хадвигера», Труды Лондонского математического общества , 7 (1): 161–195, doi : 10.1112/plms/s3-7.1.161

[gallai-1-5] Галлай, Т. (1963), «Критище Графен I», Опубл. Математика. Инст. Венгрия. акад. наук. , 8 : 165–192

[gallai-2-6] Галлай, Т. (1963), «Критище Графен II», Опубл. Математика. Инст. Венгрия. акад. наук. , 8 : 373–395

[stehlik-7] Стелик, Матей (2003), «Критические графы со связными дополнениями», Журнал комбинаторной теории , серия B, 89 (2): 189–194, doi : 10.1016/S0095-8956(03)00069-8 , MR 2017723

[hajos-8] Хайос, Г. (1961), «О конструкции не $-n-$ раскрашиваемых графов», Wiss. З. Мартина Лютера Univ. Галле-Виттенберг Математика-Природа. Серия , 10 : 116–117

[erdos-9] Эрдеш, Пол (1967), «Проблема 2», Теория графов , Proc. Коллок., Тихань, с. 361

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]