Однозначно раскрашиваемый граф

Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) k-раскраску (с точностью до перестановки цветов).
Примеры
Полный граф является однозначно раскрашиваемым, поскольку существует только одна допустимая раскраска — каждой вершине назначается свой цвет.
Любое k-дерево однозначно раскрашиваемо в (k + 1) цветов. Однозначно раскрашиваемы в 4 цвета планарные графы — это в точности графы Аполлония, то есть планарные 3-деревья.
Свойства
Некоторые свойства однозначно k-раскрашиваемого графа G с n вершинами и m рёбрами:
Связанные концепции
Минимальное несовершенство
Минимально несовершенный граф — это граф, в котором любой подграф является совершенным. Удаление любой вершины из минимально несовершенного графа оставляет однозначно раскрашиваемый подграф.
Однозначная раскраска рёбер
Однозначно рёберно-раскрашиваемый граф — это рёберно k-цветный граф, допускающий только одну (правильную) рёберную k-раскраску с точностью до перестановки цветов. Только пути и циклы допускают однозначную рёберную 2-раскраску. Для любого значения k звёзды K1,k являются однозначно рёберно k-раскрашиваемыми графами. Однако Вильсон выдвинул гипотезу, а Томасон доказал, что при k ≥ 4 это единственные члены этого семейства. Существуют, однако, однозначно рёберно 3-раскрашиваемые графы, не попадающий в эту классификацию, как, например, граф треугольной пирамиды.
Если кубический граф однозначно рёберно 3-раскрашиваем, он должен иметь в точности три гамильтонова цикла, образованного рёбрами двух (из трёх) цветов, однако некоторые кубические графы только с тремя гамильтоновыми циклами однозначной рёберной 3-раскраски не имеют. Любой простой планарный кубический граф, допускающий единственную рёберную 3-раскраску, содержит треугольник, но Тат заметил, что обобщённый граф Петерсена G(9,2) является непланарным графом без треугольников, однако он однозначно рёберно 3-раскрашиваем. Много лет этот граф был единственным примером таких графов (см.статьи Болобаша и Швенка), но теперь известно бесконечно много непланарных кубических графов без треугольников, имеющих однозначную рёберную 3-раскраску.
Однозначная полная раскраска
Однозначно тотально раскрашиваемый граф — это тотально k-цветный граф, допускающий только одну (правильную) тотальную k-раскраску (с точностью до перестановки цветов).
Пустые графы, пути и циклы с длиной, делящейся на 3, являются однозначно тотально раскрашиваемыми графами. Махмудиан и Шокроллахи высказали гипотезу, что только эти графы и составляют семейство.
Некоторые свойства однозначно тотально k-раскрашиваемого графа G с n вершинами:
Здесь χ″(G) — тотальное хроматическое число; Δ(G) — максимальная степень, а δ(G) — минимальная степень.