Введение
Граф с единственным возможным раскрашиванием
В теории графов уникально раскрашиваемый граф — это k-хроматический граф, который имеет только одну возможную (правильную) k-раскраску с точностью до перестановки цветов. Эквивалентно, существует только один способ разбить его вершины на k независимых множеств и не существует способа разбить их на k − 1 независимых множеств.
Примеры
Полный граф однозначно раскрашиваем, поскольку единственная правильная раскраска — это такая, которая присваивает каждой вершине различный цвет. Каждое k-дерево однозначно (k + 1)-раскрашиваемо. Известно, что единственно 4-раскрашиваемыми планарными графами являются ровно сети Аполлония, то есть планарные 3-деревья. Каждый связный двудольный граф однозначно 2-раскрашиваем. Его 2-раскраску можно получить, произвольно выбрав начальную вершину, раскрасив вершины на четном расстоянии от начальной вершины одним цветом и вершины на нечетном расстоянии от начальной вершины другим цветом.
Минимальное несовершенство
Минимальный несовершенный граф — это граф, в котором каждый подграф совершенен. Удаление любой вершины из минимального несовершенного графа оставляет однозначно раскрашиваемый подграф.
Уникальная окрашиваемость краев
Уникально краеокрашиваемый граф — это k-краевой хроматический граф, имеющий только одну возможную (собственную) k-краевую раскраску с точностью до перестановки цветов. Единственными уникально 2-краеокрашиваемыми графами являются пути и циклы. Для любого k звёзды K1,k являются уникально k-краеокрашиваемыми. Более того, было предположено и доказано, что при k ≥ 4 они также являются единственными элементами этого семейства. Однако существуют уникально 3-краеокрашиваемые графы, которые не подпадают под эту классификацию, например, граф треугольной пирамиды. Если кубический граф имеет уникальную 3-краевую раскраску, он должен иметь ровно три гамильтоновых цикла, образованных рёбрами, окрашенными двумя из трёх его цветов, но некоторые кубические графы, имеющие только три гамильтоновых цикла, не являются уникально 3-краеокрашиваемыми. Каждый простой планарный кубический граф, который является уникально 3-краеокрашиваемым, содержит треугольник, но было замечено, что обобщённый граф Петерсена G(9,2) является непланарным, лишённым треугольников и уникально 3-краеокрашиваемым. В течение многих лет он был единственным известным графом такого типа, и предполагалось, что он единственный, но сейчас известно бесконечно много лишённых треугольников непланарных кубических графов, которые являются уникально 3-краеокрашиваемыми.