Some Complexity Considerations on the Uniqueness of Graph Colouring

For some well-known NP-complete problems, linked to the colourability of a graph, we study the variation which consists in asking about the uniqueness of a solution (up to permutations of the colours). In particular, we show that the decision problems Unique k-Colouring (U-k-COL) with k > 3 and Unique Colouring (U-COL), have equivalent complexities, up to polynomials, as Unique Satisfiability (U-SAT) and Unique One-in-Three Satisfiability (U-1-3-SAT) by establishing polynomial reductions relating these four problems. As a consequence, all are co-NP-hard (or, equivalently, NP-hard with respect to Turing reductions) and belong to the complexity class DP. We also consider the problem Unique Optimal Colouring (U-OCOL) and show that it belongs to L^NP (also denoted Θ₂).