Точная раскраска

Точная раскраска — это раскраска вершин, в которой каждая пара цветов появляется ровно один раз на паре смежных вершин, разбиение вершин графа на непересекающиеся независимые множества. Таким образом, для каждой пары различных независимых множеств в разбиении существует только одно ребро, концы которого принадлежат обоим множествам^[1]^[2].

Полные графы, расщепления и эйлеровы циклы[править]

Любой полный граф K_n с n вершинами имеет точную раскраску n цветами, которая получается путём задания каждой вершине отдельного цвета. Также любой граф с n-цветной точной раскраской можно получить при помощи расщепления полного графа путём распадения на частицы каждой вершины на независимое множество и переключения каждого ребра, смежного вершине, ровно на одного члена соответствующего независимого множества^[1]^[2]

Если k нечётно, путь или цикл с $(\binom{k}{2})$ рёбрами имеет точную раскраску, которая получается с помощью формирования точной раскраски полного графа K_k и нахождения затем эйлерова цикла этого полного графа. Например, путь с тремя рёбрами имеет полную 3-раскраску^[2].

Связанные виды раскрасок[править]

Точные раскраски тесно связаны с гармоническими раскрасками (каждая пара цветов появляется максимум один раз) и полными раскрасками, поэтому точная раскраска одновременно гармоническая и полная. Граф G с n вершинами и m рёбрами имеет гармоничную k-раскраску тогда и только тогда, когда $m ⩽ (\binom{k}{2})$ и граф, образованный из G путём добавления $(\binom{k}{2}) - m$ изолированных рёбер имеет точную раскраску. Граф G с теми же параметрами имеет полную k-раскраску тогда и только тогда, когда $m ⩾ (\binom{k}{2})$ и существует подграф H графа G с точной k-раскраской, в которой каждое ребро графа $G - H$ имеет концы с разными цветами. Необходимость условия на рёбра $G - H$ показывается примером цикла с четырьмя вершинами, который имеет подграф с точной 3-раскраской (путь из трёх рёбер), но сам полной 3-раскраски не имеет^[2].

Вычислительная сложность[править]

Задача определения, имеет ли заданный граф точную раскраску, NP-полна даже для случая, когда граф является деревом^[1]^[3]. Однако задача может быть решена за полиномиальное время для деревьев ограниченной степени^[1]^[4].

Примечания[править]

↑ ^1,0 ^1,1 ^1,2 ^1,3 Edwards, 2005, с. 275–310.
↑ ^2,0 ^2,1 ^2,2 ^2,3 Edwards, 2010, с. 94–114.
↑ Edwards, McDiarmid, 1995, с. 133–144.
↑ Edwards, 1996, с. 15–28.

Литература[править]

Keith Edwards. Detachments of complete graphs // Combinatorics, Probability and Computing. — 2005. — Т. 14, вып. 3. — С. 275–310. — doi:10.1017/S0963548304006558.
Keith Edwards. Achromatic number of fragmentable graphs // Journal of Graph Theory. — 2010. — Т. 65, вып. 2. — С. 94–114. — doi:10.1002/jgt.20468.
Keith Edwards, Colin McDiarmid. The complexity of harmonious colouring for trees // Discrete Applied Mathematics. — 1995. — Т. 57, вып. 2—3. — С. 133–144. — doi:10.1016/0166-218X(94)00100-R.
Keith Edwards. The harmonious chromatic number of bounded degree trees // Combinatorics, Probability and Computing. — 1996. — Т. 5, вып. 1. — С. 15–28. — doi:10.1017/S0963548300001802.

[_bee96b05031dda31-1] 1,0 ^1,1 ^1,2 ^1,3 Edwards, 2005, с. 275–310.

[_7e940a59ad30ca44-2] 2,0 ^2,1 ^2,2 ^2,3 Edwards, 2010, с. 94–114.

[_1702db187944f988-3] Edwards, McDiarmid, 1995, с. 133–144.

[_6fe22e3afb3ba171-4] Edwards, 1996, с. 15–28.

[1]

[2]

[3]

[4]