List 3-coloring P_t-free graphs with no induced 1-subdivision of K₁ , s

DOI10.1016/J.DISC.2020.112086MaRDI QIDQ2198407zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Publication date 10 September 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

coloringdominating setforbidden induced subgraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: Let $s$ and $t$ be positive integers. We use $P_t$ to denote the path with $t$ vertices and $K_{1,s}$ to denote the complete bipartite graph with parts of size $1$ and $s$ respectively. The one-subdivision of $K_{1,s}$ is obtained by replacing every edge $u,v$ of $K_{1,s}$ by two edges $u,w$ and $v,w$ with a new vertex $w$. In this paper, we give a polynomial-time algorithm for the list-three-coloring problem restricted to the class of $P_t$-free graph with no induced 1-subdivision of $K_{1,s}$.

Review text

In this paper, a polynomial-time algorithm is given for the list 3-coloring problem restricted to the class of \(P_t\)-free graph with no induced 1-subdivision of \(K_{1,s}\). This complements several other partial results on a problem, which is well-known to be NP-hard in general.

Recommendations

• List k-colouring P_t-free graphs: a mim-width perspective
• Colouring \((P_r + P_s)\)-free graphs
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Narrowing the complexity gap for colouring \((C_{s},P_{t})\)-free graphs

Cites work

• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Coloring graphs without short cycles and long induced paths
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Four-coloring \(P_6\)-free graphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• The complexity of colouring problems on dense graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices

Cited in

(13)

• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• List k-colouring P_t-free graphs: a mim-width perspective
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• Bounding the mim‐width of hereditary graph classes
• Bounding the Mim-Width of Hereditary Graph Classes.
• Solving problems on generalized convex graphs via mim-width
• List-3-coloring ordered graphs with a forbidden induced subgraphs
• List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
• Solving problems on generalized convex graphs via mim-width

This page was built for publication: List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)

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