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

Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) k-раскраску (с точностью до перестановки цветов).

Примеры

Полный граф является однозначно раскрашиваемым, поскольку существует только одна допустимая раскраска — каждой вершине назначается свой цвет.

Любое k-дерево однозначно раскрашиваемо в (k + 1) цветов. Однозначно раскрашиваемы в 4 цвета планарные графы — это в точности графы Аполлония, то есть планарные 3-деревья^[1].

Свойства

Некоторые свойства однозначно k-раскрашиваемого графа G с n вершинами и m рёбрами:

1. m ≥ (k - 1) n - k(k-1)/2 ^[2][3]

Связанные концепции

Минимальное несовершенство

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

Однозначная раскраска рёбер

Однозначная 3-раскраска рёбер обобщённого графа Петерсена G(9,2)

Однозначно рёберно-раскрашиваемый граф — это рёберно k-цветный граф, допускающий только одну (правильную) рёберную k-раскраску с точностью до перестановки цветов. Только пути и циклы допускают однозначную рёберную 2-раскраску. Для любого значения k звёзды K_1,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 вершинами:

1. χ″(G) = Δ(G) + 1 unless G = K₂^[11]
2. Δ(G) ≤ 2 δ(G).^[11]
3. Δ(G) ≤ n/2 + 1.^[12]

Здесь χ″(G) — тотальное хроматическое число; Δ(G) — максимальная степень, а δ(G) — минимальная степень.