List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)

DOI10.1016/j.disc.2020.112086zbMath1471.05033arXiv2006.03009MaRDI QIDQ2198407

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

dominating set; forbidden induced subgraphs; coloring

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)