Closing Complexity Gaps for Coloring Problems on H-Free Graphs
From MaRDI portal
Publication:4909517
DOI10.1007/978-3-642-35261-4_5zbMath1260.68155OpenAlexW2151059773MaRDI QIDQ4909517
Daniël Paulusma, Jian Song, Petr A. Golovach
Publication date: 21 March 2013
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-35261-4_5
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
List coloring in the absence of two subgraphs, Colouring of graphs with Ramsey-type forbidden subgraphs, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs