A colouring of a graph G=(V,E) is a mapping c\colon V\to \{1,2,\ldots\} such that c(u)\neq c(v) for every two adjacent vertices u and v of G. The {\sc List k-Colouring problem is to decide whether a graph G=(V,E) with a list L(u)\subseteq \{1,\ldots,k\} for each u\in V has a colouring c such that c(u)\in L(u) for every u\in V. Let P_t be the path on t vertices and let K_{1,s}^1 be the graph obtained from the (s+1)-vertex star K_{1,s} by subdividing each of its edges exactly once.Recently, Chudnovsky, Spirkl and Zhong  proved that List 3-Colouring is polynomial-time solvable for (K_{1,s}^1,P_t)-free graphs for every t\geq 1 and s\geq 1. We generalize their result to List k-Colouring for every k\geq 1. Our result also generalizes the known result that for every k\geq 1 and s\geq 0, List k-Colouring is polynomial-time solvable for (sP_1+P_5)-free graphs  . We show our result by proving  that for every k\geq 1, s\geq 1, t\geq 1, the class of (K_k,K_{1,s}^1,P_t)-free graphs has bounded mim-width and that a corresponding branch decomposition is "quickly computable"  .
A colouring of a graph G=(V,E) is a mapping c\colon V\to \{1,2,\ldots\} such that c(u)\neq c(v) for every two adjacent vertices u and v of G. The {\sc List k-Colouring problem is to decide whether a graph G=(V,E) with a list L(u)\subseteq \{1,\ldots,k\} for each u\in V has a colouring c such that c(u)\in L(u) for every u\in V. Let P_t be the path on t vertices and let K_{1,s}^1 be the graph obtained from the (s+1)-vertex star K_{1,s} by subdividing each of its edges exactly once.Recently, Chudnovsky, Spirkl and Zhong (DM 2020) proved that List 3-Colouring is polynomial-time solvable for (K_{1,s}^1,P_t)-free graphs for every t\geq 1 and s\geq 1. We generalize their result to List k-Colouring for every k\geq 1. Our result also generalizes the known result that for every k\geq 1 and s\geq 0, List k-Colouring is polynomial-time solvable for (sP_1+P_5)-free graphs , which was proven for s=0 by Ho\`ang, Kami\'nski, Lozin, Sawada, and Shu (Algorithmica 2010) and for every s\geq 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\geq 1, s\geq 1, t\geq 1, the class of (K_k,K_{1,s}^1,P_t)-free graphs has bounded mim-width and that a corresponding branch decomposition is "quickly computable" for these graphs .
A
(DM 2020)
A
, which was proven for s=0 by Ho\`ang, Kami\'nski, Lozin, Sawada, and Shu (Algorithmica 2010) and for every s\geq 1 by Couturier, Golovach, Kratsch and Paulusma (Algorithmica 2015)
A
boundedness of an underlying width parameter. Namely, we show
A
for these graphs