Точная окраска - Exact coloring

Пример точной раскраски с 7 цветами и 14 вершинами

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

Полные графы, отряды и туры Эйлера

Точная окраска полный график K₆

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

Когда k является нечетное число, Путь или цикл с ${ displaystyle { tbinom {k} {2}}}$ ребра имеет точную раскраску, полученную путем формирования точной раскраски полного графа K_k а затем найти Эйлер тур этого полного графа. Например, путь с тремя ребрами имеет полную 3-раскраску.^[2]

Похожие виды окраски

Точные раскраски тесно связаны с гармоничные расцветки (раскраски, в которых каждая пара цветов встречается не более одного раза) и полные раскраски (раскраски, в которых каждая пара цветов встречается хотя бы один раз). Понятно, что точная окраска - это окраска, одновременно гармоничная и завершенная. График г с участием п вершины и м края имеет гармоничный k-раскрашивание тогда и только тогда, когда ${ Displaystyle м leq { tbinom {к} {2}}}$ и граф, сформированный из г добавлением ${ displaystyle { tbinom {k} {2}} - м}$ изолированные ребра имеют точную раскраску. График г с такими же параметрами имеет полный k-раскрашивание тогда и только тогда, когда ${ Displaystyle м geq { tbinom {к} {2}}}$ и существует подграф ЧАС из г с точным k-раскраска, в которой каждый край г − ЧАС имеет конечные точки разной окраски. Необходимость выполнения условия на краях г − ЧАС показан на примере цикла с четырьмя вершинами, который имеет подграф с точной 3-раскраской (трехреберный путь), но сам не имеет полной 3-раскраски.^[2]

Вычислительная сложность

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

использованная литература