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

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

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

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

# m ≥ (k — 1) n — k (k -1)/2  

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

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

Однозначне розфарбування ребер
узагальненого графа Петерсена G(9,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, крім випадку G = K2.
# Δ(G) ≤ 2 δ(G).
# Δ(G) ≤ n/2 + 1.

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

Примітки


Література

* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* . Як процитовано в Белкастро й Гааса .
* 
* . Як процитовано в Томасона .


Посилання
* 
