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

DOI10.1016/J.IPL.2021.106168MaRDI QIDQ2234796zbMATH OpenOpenAlexFDO

Authors Nick Brettell, Jake Horsfield, Andrea Munaro, Daniël Paulusma

Publication date 19 October 2021

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.01590

zbMATH Keywords

colouringgraph algorithmshereditary graph classmim-width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Abstract: A colouring of a graph $G=(V,E)$ is a mapping $ccolonVo1,2,ldots$ such that $c(u)eqc(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)subseteq1,ldots,k$ for each $uinV$ has a colouring $c$ such that $c(u)inL(u)$ for every $uinV$. 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 $tgeq1$ and $sgeq1$. We generalize their result to List $k$-Colouring for every $kgeq1$. Our result also generalizes the known result that for every $kgeq1$ and $sgeq0$, List $k$-Colouring is polynomial-time solvable for $(s{P}_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 $sgeq1$ 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 $kgeq1$, $sgeq1$, $tgeq1$, 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.

Recommendations

• Colouring \((P_r + P_s)\)-free graphs
• List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
• List coloring in the absence of a linear forest
• Narrowing the complexity gap for colouring \((C_{s},P_{t})\)-free graphs
• \(H\)-colouring \(P_t\)-free graphs in subexponential time

Cites work

• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• scientific article; zbMATH DE number 7651174 (Why is no real title available?)
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Bounding the Mim-Width of Hereditary Graph Classes.
• Clique-width for hereditary graph classes
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Coloring graphs without short cycles and long induced paths
• Colouring \((P_r + P_s)\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Edge dominating set and colorings on graphs with fixed clique-width
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Graph classes with structured neighborhoods and algorithmic applications
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Known algorithms on graphs of bounded treewidth are probably optimal
• List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• List coloring in the absence of a linear forest
• Mim-width. I. Induced path problems
• Mim-width. II. The feedback vertex set problem
• Mim-width. III. Graph powers and generalized distance domination problems
• More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Rank-width: algorithmic and structural results
• Recent developments on graphs of bounded clique-width
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• The Complexity of Coloring Circular Arcs and Chords
• The behavior of clique-width under graph operations and graph transformations
• The point-set embeddability problem for plane graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices

Cited in

(14)

• Odd cycle transversal on P₅-free graphs in polynomial time
• Solving problems on generalized convex graphs via mim-width
• XNLP-completeness for parameterized problems on graphs with a linear structure
• On the hardness of generalized domination problems parameterized by mim-width
• Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• XNLP-completeness for parameterized problems on graphs with a linear structure
• List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
• List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
• Solving problems on generalized convex graphs via mim-width
• Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
• Finding induced subgraphs from graphs with small mim-width
• New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
• Bounding the mim‐width of hereditary graph classes

This page was built for publication: List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2234796)