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

02.04.2021

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

Примеры

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

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

Свойства

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

  • m ≥ (k - 1) n - k(k-1)/2
  • Связанные концепции

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

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

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

    Однозначно рёберно-раскрашиваемый граф — это рёберно 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) + 1 unless G = K2
  • Δ(G) ≤ 2 δ(G).
  • Δ(G) ≤ n/2 + 1.
  • Здесь χ″(G) — тотальное хроматическое число; Δ(G) — максимальная степень, а δ(G) — минимальная степень.


    Имя:*
    E-Mail:
    Комментарий: