Publication:2770587
From MaRDI portal
zbMath0981.05037MaRDI QIDQ2770587
Gerhard J. Woeginger, Jiří Sgall
Publication date: 13 February 2002
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
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, 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, 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, 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
