Skip to Main content Skip to Navigation
Conference papers

Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

Konrad K. Dabrowski 1 François Dross 2 Matthew Johnson 1 Daniël Paulusma 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01481412
Contributor : François Dross <>
Submitted on : Monday, October 12, 2020 - 3:18:52 PM
Last modification on : Friday, November 20, 2020 - 3:26:13 PM
Long-term archiving on: : Wednesday, January 13, 2021 - 7:07:17 PM

File

1506.06564v5.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

337

Files downloads

50