Improved Complexity Results on k-Coloring P t -Free Graphs
From MaRDI portal
Publication:2849942
DOI10.1007/978-3-642-40313-2_49zbMath1400.68075OpenAlexW1691067280MaRDI QIDQ2849942
Publication date: 20 September 2013
Published in: Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-40313-2_49
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A new characterization of \(P_k\)-free graphs, List coloring in the absence of two subgraphs, Complexity of coloring graphs without paths and cycles, Vertex coloring of graphs with few obstructions, Colouring of graphs with Ramsey-type forbidden subgraphs, Coloring graphs without short cycles and long induced paths, Coloring graphs characterized by a forbidden subgraph, Polynomial cases for the vertex coloring problem, Closing complexity gaps for coloring problems on \(H\)-free graphs, Three-coloring and list three-coloring of graphs without induced paths on seven vertices