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

DOI10.1016/J.IPL.2021.106168zbMATH Open1476.05050arXiv2008.01590OpenAlexW3122713457MaRDI QIDQ2234796FDOQ2234796

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)

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.

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

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

zbMATH Keywords

colouringgraph algorithmshereditary graph classmim-width

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Solving problems on generalized convex graphs via mim-width
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
• On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
• 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
• 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)