Меню
Главная
Случайная статья
Настройки
|
Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) k-раскраску (с точностью до перестановки цветов).
Содержание
Примеры
Полный граф является однозначно раскрашиваемым, поскольку существует только одна допустимая раскраска — каждой вершине назначается свой цвет.
Любое k-дерево однозначно раскрашиваемо в (k + 1) цветов. Однозначно раскрашиваемы в 4 цвета планарные графы — это в точности графы Аполлония, то есть планарные 3-деревья[1].
Свойства
Некоторые свойства однозначно k-раскрашиваемого графа G с n вершинами и m рёбрами:
- m (k - 1) n - k(k-1)/2 [2][3]
Связанные концепции
Минимальное несовершенство
Минимально несовершенный граф — это граф, в котором любой подграф является совершенным. Удаление любой вершины из минимально несовершенного графа оставляет однозначно раскрашиваемый подграф.
Однозначная раскраска рёбер
Однозначно рёберно-раскрашиваемый граф — это рёберно k-цветный граф, допускающий только одну (правильную) рёберную k-раскраску с точностью до перестановки цветов. Только пути и циклы допускают однозначную рёберную 2-раскраску. Для любого значения k звёзды K1,k являются однозначно рёберно k-раскрашиваемыми графами. Однако Вильсон [4] выдвинул гипотезу, а Томасон[5] доказал, что при k 4 это единственные члены этого семейства. Существуют, однако, однозначно рёберно 3-раскрашиваемые графы, не попадающий в эту классификацию, как, например, граф треугольной пирамиды.
Если кубический граф однозначно рёберно 3-раскрашиваем, он должен иметь в точности три гамильтонова цикла, образованного рёбрами двух (из трёх) цветов, однако некоторые кубические графы только с тремя гамильтоновыми циклами однозначной рёберной 3-раскраски не имеют[6].
Любой простой планарный кубический граф, допускающий единственную рёберную 3-раскраску, содержит треугольник[1], но Тат[7] заметил, что обобщённый граф Петерсена G(9,2) является непланарным графом без треугольников, однако он однозначно рёберно 3-раскрашиваем. Много лет этот граф был единственным примером таких графов (см.статьи Болобаша[8] и Швенка[9]), но теперь известно бесконечно много непланарных кубических графов без треугольников, имеющих однозначную рёберную 3-раскраску[6].
Однозначная полная раскраска
Однозначно тотально раскрашиваемый граф — это тотально k-цветный граф, допускающий только одну (правильную) тотальную k-раскраску (с точностью до перестановки цветов).
Пустые графы[англ.]*, пути и циклы с длиной, делящейся на 3, являются однозначно тотально раскрашиваемыми графами.
Махмудиан и Шокроллахи[10] высказали гипотезу, что только эти графы и составляют семейство.
Некоторые свойства однозначно тотально k-раскрашиваемого графа G с n вершинами:
- (G) = (G) + 1 unless G = K2[11]
- (G) 2 (G).[11]
- (G) n/2 + 1.[12]
Здесь (G) — тотальное хроматическое число; (G) — максимальная степень, а (G) — минимальная степень.
Примечания
- 1 2 Fowler, 1998.
- Truszczyski, 1984.
- Xu, 1990.
- Wilson, 1976.
- Thomason, 1978.
- 1 2 Belcastro, Haas, 2015.
- Tutte, 1976.
- Bollobs, 1978.
- Schwenk, 1989.
- Mahmoodian, Shokrollahi, 1995.
- 1 2 Akbari, Behzad, Hajiabolhassan, Mahmoodian, 1997.
- Akbari, 2003.
Литература- S. Akbari. Two conjectures on uniquely totally colorable graphs // Discrete Mathematics. — 2003. — Т. 266, вып. 1-3. — С. 41–45. — doi:10.1016/S0012-365X(02)00797-5.
- S. Akbari, M. Behzad, H. Hajiabolhassan, E. S. Mahmoodian. Uniquely total colorable graphs // Graphs and Combinatorics. — 1997. — Т. 13, вып. 4. — С. 305–314. — doi:10.1016/S0012-365X(02)00797-5.
- Sarah-Marie Belcastro, Ruth Haas. Triangle-free uniquely 3-edge colorable cubic graphs // Contributions to Discrete Mathematics. — 2015. — Т. 10, вып. 2. — С. 39–44. — arXiv:1508.06934.
- Bla Bollobs. Extremal Graph Theory. — Academic Press, 1978. — Т. 11. — (LMS Monographs).
- Christopher J. Hillar, Troels Windfeldt. Algebraic characterization of uniquely vertex colorable graphs // Journal of Combinatorial Theory. — 2008. — Т. 98, вып. 2. — С. 400–414. — doi:10.1016/j.jctb.2007.08.004.
- Allen J. Schwenk. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // Journal of Combinatorial Theory. — 1989. — Т. 47, вып. 1. — С. 53–59. — doi:10.1016/0095-8956(89)90064-6.
- Shao Ji Xu. The size of uniquely colorable graphs // Journal of Combinatorial Theory. — 1990. — Т. 50, вып. 2. — С. 319–320. — doi:10.1016/0095-8956(90)90086-F.
Ссылки
|
|