Критический график - Critical graph
В теория графов, а критический граф это график г в котором каждая вершина или ребро является критический элемент, то есть если его удаление уменьшает хроматическое число из г. Такое уменьшение не может быть более чем на 1.
Вариации
А k-критический график критический граф с хроматическим числом k; график г с хроматическим числом k является k-верхкритический если каждая из его вершин является критическим элементом. Критические графики - это минимальный членов с точки зрения хроматического числа, что является очень важной мерой в теории графов.
Некоторые свойства k-критический график г с участием п вершины и м края:
- г есть только один составная часть.
- г конечно (это Теорема де Брейна – Эрдеша из де Брюйн и Эрдеш, 1951 г. ).
- δ (г) ≥ k - 1, то есть каждая вершина смежна не менее чем с k - еще 1. Сильнее, г является (k − 1)-реберный. Увидеть Ловас (1992)
- Если г является (k - 1) -регулярный, что означает, что каждая вершина смежна точно с k - еще 1, затем г либо Kk или нечетный цикл . Это Теорема Брукса; увидеть Брукс и Тутт (1941) ).
- 2 м ≥ (k − 1) п + k − 3 (Дирак 1957 ).
- 2 м ≥ (k − 1) п + [(k − 3)/(k2 − 3)] п (Галлай 1963a ).
- Либо г может быть разложен на два критических графа меньшего размера с ребром между каждой парой вершин, которое включает по одной вершине из каждого из двух подграфов, или г имеет как минимум 2k - 1 вершина (Галлай 1963b ). Сильнее, либо г имеет разложение этого типа, или для каждой вершины v из г Существует k-раскраска в которой v является единственной вершиной своего цвета, а любой другой цветовой класс имеет не менее двух вершин (Stehlík 2003 ).
Граф G является вершинно-критическим тогда и только тогда, когда для каждой вершины v, существует оптимальная правильная раскраска, в которой v одноэлементный цветовой класс.
Так как Хаджос (1961) показал, каждый k-критический граф может быть сформирован из полный график Kk путем объединения Строительство Hajós с операцией, которая идентифицирует две несмежные вершины. Построенные таким образом графы всегда требуют k цвета в любой правильной расцветке.
А двукритический граф является связным графом, в котором удаление любой пары смежных вершин уменьшает хроматическое число на два. Одна из открытых проблем - определить, Kk единственный дважды критичный k-хроматический график.[1]
Смотрите также
использованная литература
Источники
- Brooks, R.L .; Тутте, W. T. (1941), "О раскраске узлов сети", Труды Кембриджского философского общества, 37 (02): 194–197, Дои:10.1017 / S030500410002168X
- де Брёйн, Н.Г.; Эрдеш, П. (1951), «Проблема цвета для бесконечных графов и проблема теории отношений», Nederl. Акад. Wetensch. Proc. Сер. А, 54: 371–373. (Indag. Математика. 13.)
- Дирак, Г.А. (1957), «Теорема Р. Л. Брукса и гипотеза Х. Хадвигера», Труды Лондонского математического общества, 7 (1): 161–195, Дои:10.1112 / плмс / с3-7.1.161
- Эрдеш, Пол (1967), «Проблема 2», В теории графов, Proc. Коллок., Тихань, стр. 361CS1 maint: ref = harv (ссылка на сайт)
- Галлай, Т. (1963a), "Kritische Graphen I", Publ. Математика. Inst. Hungar. Акад. Sci., 8: 165–192
- Галлай, Т. (1963b), "Kritische Graphen II", Publ. Математика. Inst. Hungar. Акад. Sci., 8: 373–395
- Хайос, Г. (1961), "Über eine Konstruktion nicht" п-färbbarer Graphen ", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Рейхе, 10: 116–117.
- Jensen, T. R .; Тофт, Б. (1995), Задачи раскраски графов, Нью-Йорк: Wiley-Interscience, ISBN 0-471-02865-7
- Stehlík, Matěj (2003), "Критические графы со связными дополнениями", Журнал комбинаторной теории, Серия B, 89 (2): 189–194, Дои:10.1016 / S0095-8956 (03) 00069-8, Г-Н 2017723.
- Ловас, Ласло (1992), «Решение упражнения 9.21», Комбинаторные задачи и упражнения (второе издание), Северная Голландия
- Стибиц, Майкл; Туза, Жолт; Войт, Маргит (6 августа 2009 г.), «В списке критических графов», Дискретная математика, Эльзевьер, 309 (15): 4931–4941, Дои:10.1016 / j.disc.2008.05.021