В теории графов , А критический граф является графом G , в котором каждая вершина или ребро является критическим элементом , то есть, если его удаление уменьшает хроматическое число из G . Такое уменьшение не может быть более чем на 1.
Варианты [ править ]
К Критическим графами являются критическим графом с хроматическим числом к ; граф G с хроматическим числом k является k -вершинно-критическим, если каждая его вершина является критическим элементом. Критические графы - это минимальные элементы с точки зрения хроматического числа, что является очень важной мерой в теории графов.
Некоторые свойства k -критического графа G с n вершинами и m ребрами:
- G имеет только один компонент .
- G конечна (это теорема де Брейна – Эрдеша из работы de Bruijn & Erds 1951 ).
- δ ( G ) ≥ k - 1, то есть каждая вершина смежна не менее чем с k - 1 другими. Более того, G ( k - 1) -связна по ребрам . См. Ловас (1992).
- Если G является ( к - 1) -регулярными , то есть каждая вершина смежно точно K - 1 других, то G является либо К к или нечетному циклу . Это теорема Брукса ; см. Brooks & Tutte (1941) ).
- 2 m ≥ ( k - 1) n + k - 3 ( Дирак, 1957 ).
- 2 m ≥ ( k - 1) n + [( k - 3) / ( k 2 - 3)] n ( Галлай, 1963a ).
- Либо G может быть разложен на два меньших критических графа, с ребром между каждой парой вершин, которое включает по одной вершине из каждого из двух подграфов, либо G имеет по крайней мере 2 k - 1 вершину ( Gallai 1963b ). Сильнее, либо G имеет разложение этого типа, или для каждой вершины V в G есть к -раскраска , в которой v является единственной вершиной своего цвета и любого другого цвета класса имеет по крайней мере две вершины ( Stehlík 2003 ).
Граф G является вершинно-критическим тогда и только тогда, когда для каждой вершины v существует оптимальная правильная раскраска, в которой v - одноэлементный цветовой класс.
Как показал Хайос (1961) , каждый k -критический граф может быть сформирован из полного графа K k путем объединения конструкции Хайоса с операцией, которая идентифицирует две несмежные вершины. Построенные таким образом графы всегда требуют k цветов в любой правильной раскраске.
Двойной критический граф является связным графом , в котором удаление любой пары смежных вершин уменьшает хроматическое число на два. Одна из открытых проблем - определить, является ли K k единственным дважды критическим k -хроматическим графом. [1]
См. Также [ править ]
Ссылки [ править ]
 | Викискладе есть медиафайлы по теме критического графа . |
Источники [ править ]
- Брукс, Р.Л .; Тутт, У. Т. (1941), «О раскрашивании узлов сети», Труды Кембриджского философского общества , 37 (2): 194–197, DOI : 10.1017 / S030500410002168X
- de Bruijn, NG ; Эрдеш, П. (1951), "Проблема цвета для бесконечных графов и проблема теории отношений" , Nederl. Акад. Wetensch. Proc. Сер. , 54 : 371-373, DOI : 10.1016 / S1385-7258 (51) 50053-7. ( Indag. Math. 13. )
- Дирак, Г.А. (1957), «Теорема Р.Л. Брукса и гипотеза Х. Хадвигера», Труды Лондонского математического общества , 7 (1): 161–195, doi : 10.1112 / plms / s3-7.1.161
- Эрдеш, Пол (1967), «Проблема 2», по теории графов , Proc. Коллок., Тихань, стр. 361
- Галлай, Т. (1963a), "Kritische Graphen I", Publ. Математика. Inst. Hungar. Акад. Sci. , 8 : 165–192
- Галлай, Т. (1963b), "Kritische Graphen II", Publ. Математика. Inst. Hungar. Акад. Sci. , 8 : 373–395
- Hajós, G. (1961), "Uber eine Konstruktion nicht n -färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Рейхе , 10 : 116–117.
- Дженсен, TR; Тофт, Б. (1995), Проблемы раскраски графов , Нью-Йорк: Wiley-Interscience, ISBN 0-471-02865-7
- Stehlík, Матей (2003), "Критические графы с подсоединенными дополнениями", Журнал комбинаторной теории , серии B, 89 (2): 189-194, DOI : 10.1016 / S0095-8956 (03) 00069-8 , MR 2017723.
- Ловас, Ласло (1992), «Решение упражнения 9.21», Комбинаторные задачи и упражнения (второе издание) , Северная Голландия.
- Стибиц, Майкл; Туза, Жолт; Фойгт, Маргит (6 августа 2009), "О перечне критических графов", Дискретная математика , Elsevier, 309 (15): 4931-4941, DOI : 10.1016 / j.disc.2008.05.021
