We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

List k-colouring P-free graphs: a mim-width perspective

Brettell, N. and Horsfield, J. and Munaro, A. and Paulusma, D. (2022) 'List k-colouring P-free graphs: a mim-width perspective.', Information processing letters., 173 . p. 106168.


A colouring of a graph G = (V, E) is a mapping c : V → {1, 2, . . .} such that c(u) 6= c(v) for every two adjacent vertices u and v of G. The List k-Colouring problem is to decide whether a graph G = (V, E) with a list L(u) ⊆ {1, . . . , k} for each u ∈ V has a colouring c such that c(u) ∈ L(u) for every u ∈ V . Let Pt be the path on t vertices and let K1 1,s be the graph obtained from the (s + 1)-vertex star K1,s by subdividing each of its edges exactly once. Recently, Chudnovsky, Spirkl and Zhong (DM 2020) proved that List 3-Colouring is polynomialtime solvable for (K1 1,s, Pt)-free graphs for every t ≥ 1 and s ≥ 1. We generalize their result to List k-Colouring for every k ≥ 1. Our result also generalizes the known result that for every k ≥ 1 and s ≥ 0, List k-Colouring is polynomial-time solvable for (sP1 + P5)-free graphs, which was proven for s = 0 by Hoàng, Kamiński, Lozin, Sawada, and Shu (Algorithmica 2010) and for every s ≥ 1 by Couturier, Golovach, Kratsch and Paulusma (Algorithmica 2015). We show our result by proving boundedness of an underlying width parameter. Namely, we show that for every k ≥ 1, s ≥ 1, t ≥ 1, the class of (Kk, K1 1,s, Pt)-free graphs has bounded mim-width and that a corresponding branch decomposition is “quickly computable” for these graphs.

Item Type:Article
Full text:Publisher-imposed embargo until 21 July 2023.
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
File format - PDF
Publisher Web site:
Publisher statement:© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:13 July 2021
Date deposited:24 August 2021
Date of first online publication:21 July 2021
Date first made open access:21 July 2023

Save or Share this output

Look up in GoogleScholar