Однозначно розфарбовуваний граф

Однозна́чно розфарбо́вуваний граф — це k-колірний граф, що допускає тільки одне (правильне) k-розфарбування (з точністю до перестановки кольорів).

Приклади

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

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

Властивості

Деякі властивості однозначно k-розфарбовуваного графа G з n вершинами і m ребрами:

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

Пов'язані концепції

Мінімальна недосконалість

Мінімально недосконалий граф — це граф, e якому будь-який підграф є досконалим. Видалення будь-якої вершини з мінімально недосконалого графа залишає однозначно розфарбовуваний підграф.

Однозначне розфарбування ребер

Однозначне 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-розфарбування (з точністю до перестановки кольорів).

Порожні графи^[en], шляхи й цикли з довжиною, що ділиться на 3, є однозначно тотально розфарбовуваними графами. Махмудіан і Шокроллахі^[10] висунули гіпотезу, что тільки ці графи й утворюють сімейство.

Деякі властивості однозначно тотально k-розфарбовуваного графа G з n вершинами:

1. χ″(G) = Δ(G) + 1, крім випадку G = K₂^[11].
2. Δ(G) ≤ 2 δ(G)^[11].
3. Δ(G) ≤ n/2 + 1^[12].

Тут χ″(G) — тотальне хроматичне число; Δ(G) — найбільший степінь, а δ(G) — найменший степінь.