Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2016

Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

Konrad K. Dabrowski
  • Fonction : Auteur
  • PersonId : 972724
François Dross
Matthew Johnson
Daniël Paulusma

Résumé

A colouring of a graph G = (V, E) is a function c : V → {1, 2,. . .} such that c(u) = c(v) for every uv ∈ E. A k-regular list assignment of G is a function L with domain V such that for every u ∈ V , L(u) is a subset of {1, 2,. .. } of size k. A colouring c of G respects a k-regular list assignment L of G if c(u) ∈ L(u) for every u ∈ V. A graph G is k-choosable if for every k-regular list assignment L of G, there exists a colouring of G that respects L. We may also ask if for a given k-regular list assignment L of a given graph G, there exists a colouring of G that respects L. This yields the k-Regular List Colouring problem. For k ∈ {3, 4} we determine a family of classes G of planar graphs, such that either k-Regular List Colouring is NP-complete for instances (G, L) with G ∈ G, or every G ∈ G is k-choosable. By using known examples of non-3-choosable and non-4-choosable graphs, this enables us to classify the complexity of k-Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs and to planar graphs with no 4-cycles and no 5-cycles. We also classify the complexity of k-Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.
Fichier principal
Vignette du fichier
1506.06564v5.pdf (246.29 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01481412 , version 1 (12-10-2020)

Identifiants

Citer

Konrad K. Dabrowski, François Dross, Matthew Johnson, Daniël Paulusma. Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs. 25th International Workshop on Combinatorial Algorithms (IWOCA), Oct 2015, Verona, Italy. pp.100-111, ⟨10.1007/978-3-319-29516-9_9⟩. ⟨lirmm-01481412⟩
180 Consultations
78 Téléchargements

Altmetric

Partager

More