Точная раскраска
Точная раскраска — это раскраска вершин, в которой каждая пара цветов появляется ровно один раз на паре смежных вершин, разбиение вершин графа на непересекающиеся независимые множества. Таким образом, для каждой пары различных независимых множеств в разбиении существует только одно ребро, концы которого принадлежат обоим множествамШаблон:SfnШаблон:Sfn.
Полные графы, расщепления и эйлеровы циклы
Любой полный граф Kn с n вершинами имеет точную раскраску n цветами, которая получается путём задания каждой вершине отдельного цвета. Также любой граф с n-цветной точной раскраской можно получить при помощи расщепления полного графа путём распадения на частицы каждой вершины на независимое множество и переключения каждого ребра, смежного вершине, ровно на одного члена соответствующего независимого множестваШаблон:SfnШаблон:Sfn
Если k нечётно, путь или цикл с рёбрами имеет точную раскраску, которая получается с помощью формирования точной раскраски полного графа Kk и нахождения затем эйлерова цикла этого полного графа. Например, путь с тремя рёбрами имеет полную 3-раскраскуШаблон:Sfn.
Связанные виды раскрасок
Точные раскраски тесно связаны с гармоническими раскрасками (каждая пара цветов появляется максимум один раз) и полными раскрасками, поэтому точная раскраска одновременно гармоническая и полная. Граф G с n вершинами и m рёбрами имеет гармоничную k-раскраску тогда и только тогда, когда и граф, образованный из G путём добавления изолированных рёбер имеет точную раскраску. Граф G с теми же параметрами имеет полную k-раскраску тогда и только тогда, когда и существует подграф H графа G с точной k-раскраской, в которой каждое ребро графа имеет концы с разными цветами. Необходимость условия на рёбра показывается примером цикла с четырьмя вершинами, который имеет подграф с точной 3-раскраской (путь из трёх рёбер), но сам полной 3-раскраски не имеетШаблон:Sfn.
Вычислительная сложность
Задача определения, имеет ли заданный граф точную раскраску, NP-полна даже для случая, когда граф является деревомШаблон:SfnШаблон:Sfn. Однако задача может быть решена за полиномиальное время для деревьев ограниченной степениШаблон:SfnШаблон:Sfn.