Граф, що однозначно розфарбовується
Однозначно розфарбовуваний граф- це k-кольоровий граф, що допускає лише одну (правильну)k-розмальовку (з точністю до перестановки кольорів).
Зміст
Повний граф є однозначно розфарбовуваним, оскільки існує лише одне допустиме забарвлення - кожній вершині призначається свій колір.
Будь-якеk-дерево однозначно розфарбовується в (k+ 1) кольорів. Однозначно розфарбовуються в 4 кольори планарні графи - це точно графи Аполлонія, тобто планарні 3-дерева [1] .
Деякі властивості однозначноk-розмальовуваного графаGзnвершинами іmребрами:
Мінімальна недосконалість
Мінімально недосконалий граф- це граф, в якому будь-який підграф є досконалим. Видалення будь-якої вершини з мінімально недосконалого графа залишає підграф, що однозначно розфарбовується.
Однозначне розмальовка ребер
Однозначно реберно-розфарбовуваний граф- це реберноk-кольоровий граф, що допускає лише одну (правильну) ребернуk-розмальовку з точністю до перестановки кольорів. Тільки шляхи та цикли допускають однозначну реберну 2-розмальовку. Для будь-якого значенняkзіркиK1,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вершинами: