scientific article
From MaRDI portal
Publication:2770587
zbMath0981.05037MaRDI QIDQ2770587
Jiří Sgall, Gerhard J. Woeginger
Publication date: 13 February 2002
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (34)
4-Coloring H-Free Graphs When H Is Small ⋮ Lower and upper bounds for long induced paths in 3-connected planar graphs ⋮ Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time ⋮ Choosability of P 5-Free Graphs ⋮ Complexity of coloring graphs without paths and cycles ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ 3-colouring AT-free graphs in polynomial time ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ A New Characterization of P 6-Free Graphs ⋮ Coloring graphs without short cycles and long induced paths ⋮ 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs. ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ On the complexity of 4-coloring graphs without long induced paths ⋮ Two complexity results for the vertex coloring problem ⋮ Constructions of \(k\)-critical \(P_5\)-free graphs ⋮ List coloring in the absence of a linear forest ⋮ A new characterization of \(P_{6}\)-free graphs ⋮ Unnamed Item ⋮ A Note on k-Colorability of P 5-Free Graphs ⋮ Stable sets in \(k\)-colorable \(P_{5}\)-free graphs ⋮ Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Partitioning Graphs into Connected Parts ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ Some results on graphs without long induced paths ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ Colouring vertices of triangle-free graphs without forests ⋮ List Coloring in the Absence of a Linear Forest ⋮ Partitioning graphs into connected parts
This page was built for publication:
