Русская Википедия:Однозначно раскрашиваемый граф

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Примеры

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

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

Свойства

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

  1. m ≥ (k - 1) n - k(k-1)/2 Шаблон:SfnШаблон:Sfn

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

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

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

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

Файл:Generalized Petersen 9 2 edge coloring.svg
Однозначная 3-раскраска рёбер обобщённого графа Петерсена G(9,2)

Однозначно рёберно-раскрашиваемый граф — это рёберно k-цветный граф, допускающий только одну (правильную) рёберную k-раскраску с точностью до перестановки цветов. Только пути и циклы допускают однозначную рёберную 2-раскраску. Для любого значения k звёзды K1,k являются однозначно рёберно k-раскрашиваемыми графами. Однако Вильсон Шаблон:Sfn выдвинул гипотезу, а ТомасонШаблон:Sfn доказал, что при k ≥ 4 это единственные члены этого семейства. Существуют, однако, однозначно рёберно 3-раскрашиваемые графы, не попадающий в эту классификацию, как, например, граф треугольной пирамиды.

Если кубический граф однозначно рёберно 3-раскрашиваем, он должен иметь в точности три гамильтонова цикла, образованного рёбрами двух (из трёх) цветов, однако некоторые кубические графы только с тремя гамильтоновыми циклами однозначной рёберной 3-раскраски не имеютШаблон:Sfn. Любой простой планарный кубический граф, допускающий единственную рёберную 3-раскраску, содержит треугольникШаблон:Sfn, но ТатШаблон:Sfn заметил, что обобщённый граф Петерсена G(9,2) является непланарным графом без треугольников, однако он однозначно рёберно 3-раскрашиваем. Много лет этот граф был единственным примером таких графов (см.статьи БолобашаШаблон:Sfn и ШвенкаШаблон:Sfn), но теперь известно бесконечно много непланарных кубических графов без треугольников, имеющих однозначную рёберную 3-раскраскуШаблон:Sfn.

Однозначная полная раскраска

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

Шаблон:Не переведено 5, пути и циклы с длиной, делящейся на 3, являются однозначно тотально раскрашиваемыми графами. Махмудиан и ШокроллахиШаблон:Sfn высказали гипотезу, что только эти графы и составляют семейство.

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

  1. χ″(G) = Δ(G) + 1 unless G = K2Шаблон:Sfn
  2. Δ(G) ≤ 2 δ(G).Шаблон:Sfn
  3. Δ(G) ≤ n/2 + 1.Шаблон:Sfn

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Однозначно_раскрашиваемый_граф&oldid=10505054