Publication:4448764

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

Related Items

Unnamed Item, The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs, 3-Colorable Subclasses of $P_8$-Free Graphs, On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size, Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions, Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem, Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes, On Betti numbers of flag complexes with forbidden induced subgraphs, Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs, Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes, Colouring (P_r+P_s)-Free Graphs, Colouring H-free graphs of bounded diameter., $(2P_2,K_4)$-Free Graphs are 4-Colorable, 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, Polynomial cases 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, Connected greedy coloring of \(H\)-free graphs, Algorithms for the rainbow vertex coloring problem on graph classes, The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable, 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., The weighted coloring problem for two graph classes characterized by small forbidden induced structures, A coloring algorithm for \(4 K_1\)-free line graphs, Towards an isomorphism dichotomy for hereditary graph classes, Colouring of \((P_3 \cup P_2)\)-free graphs, On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs, Critical vertices and edges in \(H\)-free graphs, Independent feedback vertex set for \(P_5\)-free graphs, Classifying \(k\)-edge colouring for \(H\)-free graphs, On the algorithmic aspects of strong subcoloring, Contraction and deletion blockers for perfect graphs and \(H\)-free graphs, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, 3-colouring AT-free graphs in polynomial time, The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs, On coloring a class of claw-free and hole-twin-free graphs, Revising Johnson's table for the 21st century, Injective colouring for H-free graphs, On coloring a class of claw-free graphs., Graph clustering via generalized colorings, Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs, Partitioning \(H\)-free graphs of bounded diameter, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Regular pattern-free coloring, On the complexity of cd-coloring of graphs, Colouring \((P_r + P_s)\)-free graphs, Better 3-coloring algorithms: excluding a triangle and a seven vertex path, List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective, 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, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, \(H\)-colouring \(P_t\)-free graphs in subexponential time, Colouring square-free graphs without long induced paths, Efficient approximation for restricted biclique cover problems, 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, Reducing the chromatic number by vertex or edge deletions, On the chromatic number of (\(P_6\), diamond)-free graphs, Solving the clique cover problem on (bull, \(C_4\))-free graphs, Coloring graphs without short cycles and long induced paths, List coloring in the absence of two subgraphs, On the complexity of colouring antiprismatic graphs, Non-empty intersection of longest paths in \(H\)-free graphs, 3-colouring \(P_t\)-free graphs without short odd cycles, 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, Colouring square-free graphs without long induced paths., A Note on k-Colorability of P 5-Free Graphs, Unnamed Item, Approximately coloring graphs without long induced paths, Connected vertex cover for \((sP_1+P_5)\)-free graphs, Two cases of polynomial-time solvability for the coloring problem