Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs

DOI10.1007/978-3-642-16926-7_8zbMath1308.68063OpenAlexW43428552MaRDI QIDQ3057613

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

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_8

Mathematics Subject Classification ID

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 (1)

Colouring vertices of triangle-free graphs without forests

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The complexity of colouring problems on dense graphs
• The ellipsoid method and its consequences in combinatorial optimization
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Vertex colouring and forbidden subgraphs -- a survey
• On the complexity of 4-coloring graphs without long induced paths
• On Coloring Graphs without Induced Forests
• Three Complexity Results on Coloring P k -Free Graphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• Graph colorings with local constraints -- a survey
• The complexity of satisfiability problems

This page was built for publication: Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs