Publication:2770587

zbMath0981.05037MaRDI QIDQ2770587

Jiří Sgall, Gerhard J. Woeginger

Publication date: 13 February 2002

zbMATH Keywords

computational complexity; graph coloring; chromatic number; induced path

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

05C15: Coloring of graphs and hypergraphs

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Lower and upper bounds for long induced paths in 3-connected planar graphs, Complexity of coloring graphs without paths and cycles, Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time, On the parameterized complexity of coloring graphs in the absence of a linear forest, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, Two complexity results for the vertex coloring problem, Updating the complexity status of coloring graphs without a fixed induced linear forest, Colouring vertices of triangle-free graphs without forests, Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time, A new characterization of \(P_{6}\)-free graphs, Stable sets in \(k\)-colorable \(P_{5}\)-free graphs, Some results on graphs without long induced paths, Partitioning graphs into connected parts, 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs., 3-colouring AT-free graphs in polynomial time, Constructions of \(k\)-critical \(P_5\)-free graphs, List coloring in the absence of a linear forest, Certifying coloring algorithms for graphs without long induced paths, Coloring graphs without short cycles and long induced paths, On the complexity of 4-coloring graphs without long induced paths, 4-Coloring H-Free Graphs When H Is Small, 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs, Colouring Vertices of Triangle-Free Graphs, List Coloring in the Absence of a Linear Forest, Choosability of P 5-Free Graphs, Partitioning Graphs into Connected Parts, A New Characterization of P 6-Free Graphs, A Note on k-Colorability of P 5-Free Graphs