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

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

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

Когда k — нечетное число , путь или цикл с ребрами имеет точную раскраску, полученную путем формирования точной раскраски полного графа K _k и последующего нахождения эйлерова тура этого полного графа. Например, путь с тремя ребрами имеет полную 3-раскраску. ^[2]${\displaystyle {\tbinom {k}{2}}}$

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

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