WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 22, 2023
Some Complexity Considerations on the Uniqueness of Graph Colouring
Authors: ,
Abstract: 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 \geq 3$$ and Unique Colouring
(U-COL), have equivalent complexities, up to polynomials, as Unique Satisfiability (U-SAT) and Unique Onein-
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 $$Θ^{2}$$).
Search Articles
Keywords: Complexity Theory, co-NP-hardness, NP-hardness, Decision Problems, Polynomial Reduction, Turing Reduction, Uniqueness of Solution, Graph Theory, Graph Colouring, Partition into Independent Sets, Boolean Satisfiability, Satisfiability Problems
Pages: 483-493
DOI: 10.37394/23206.2023.22.54