Some Complexity Considerations on the Uniqueness of Graph Colouring - Equipe Mathématiques discrètes, codage et cryptographie Accéder directement au contenu
Article Dans Une Revue WSEAS Transactions on Mathematics Année : 2023

Some Complexity Considerations on the Uniqueness of Graph Colouring

Résumé

For some well-known NP-complete problems, linked to the satisfiability of Boolean formulas and the colourability of a graph, we study the variation which consists in asking about the uniqueness of a solution. In particular, we show that five decision problems, Unique Satisfiability (U-SAT), Unique k-Satisfiability (U-k-SAT), k ≥ 3, Unique One-in-Three Satisfiability (U-1-3-SAT), Unique k-Colouring (U-k-COL), k ≥ 3, and Unique Colouring (U-COL), have equivalent complexities, up to polynomials —when dealing with colourings, we forbid permutations of colours. As a consequence, all are NP-hard and belong to the class DP. We also consider the problems U-2-SAT, U-2-COL and Unique Optimal Colouring (U-OCOL).
Fichier non déposé

Dates et versions

hal-02287571 , version 1 (13-09-2019)

Identifiants

  • HAL Id : hal-02287571 , version 1

Citer

Olivier Hudry, Antoine Lobstein. Some Complexity Considerations on the Uniqueness of Graph Colouring. WSEAS Transactions on Mathematics, 2023, 22, pp.art. #54, 483-493. ⟨hal-02287571⟩
145 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More