Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2016

Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

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

Abstract

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
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
173 View
65 Download

Altmetric

Share

More