Publication:4448764
From MaRDI portal
zbMath1042.68639MaRDI QIDQ4448764
Gerhard J. Woeginger, Zsolt Tuza, Jan Kratochvíl, Daniel Král'
Publication date: 18 February 2004
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2204/22040254.htm
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
Related Items
Two cases of polynomial-time solvability for the coloring problem, A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs, A complexity dichotomy and a new boundary class for the dominating set problem, On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs, Complexity of coloring graphs without paths and cycles, Graph isomorphism for graph classes characterized by two forbidden induced subgraphs, Vertex coloring of graphs with few obstructions, Colouring of graphs with Ramsey-type forbidden subgraphs, A decidability result for the dominating set problem, Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time, \textsc{max-cut} and containment relations in graphs, On the parameterized complexity of coloring graphs in the absence of a linear forest, Coloring graphs characterized by a forbidden subgraph, The coloring problem for classes with two small obstructions, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, Two complexity results for the vertex coloring problem, Some new hereditary classes where graph coloring remains NP-hard, 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, Stable sets in \(k\)-colorable \(P_{5}\)-free graphs, 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs., A coloring algorithm for \(4 K_1\)-free line graphs, Towards an isomorphism dichotomy for hereditary graph classes, 3-colouring AT-free graphs in polynomial time, Closing complexity gaps for coloring problems on \(H\)-free graphs, Constructions of \(k\)-critical \(P_5\)-free graphs, List coloring in the absence of a linear forest, Domination, coloring and stability in \(P_5\)-reducible graphs, Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, On line graphs of subcubic triangle-free graphs, Boundary classes for graph problems involving non-local properties, Colouring diamond-free graphs, The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs, Coloring graphs without short cycles and long induced paths, List coloring in the absence of two subgraphs, Open Problems on Graph Coloring for Special Graph Classes, Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions, 4-Coloring H-Free Graphs When H Is Small, Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, Contraction Blockers for Graphs with Forbidden Induced Paths, max-cut and Containment Relations in Graphs, Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs, Colouring Vertices of Triangle-Free Graphs, Coloring Graphs without Short Cycles and Long Induced Paths, List Coloring in the Absence of a Linear Forest, Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs, Choosability of P 5-Free Graphs, A Note on k-Colorability of P 5-Free Graphs
