Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time

DOI10.1016/j.tcs.2011.12.076zbMath1241.05030MaRDI QIDQ417995

Daniël Paulusma, Petr A. Golovach, Hajo J. Broersma, Jian Song

Publication date: 14 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.076

zbMATH Keywords

chromatic number; triangle-free; forbidden induced subgraph

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)