scientific article; zbMATH DE number 2044943

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

Unnamed Item, On the price of independence for vertex cover, feedback vertex set and odd cycle transversal, Complexity of total dominator coloring in graphs, Reconfiguration of vertex colouring and forbidden induced subgraphs, 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, 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, 4-Coloring H-Free Graphs When H Is Small, On coloring a class of claw-free graphs., Graph clustering via generalized colorings, Forbidden induced pairs for perfectness and $\omega$-colourability of graphs, Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs, List coloring in the absence of two subgraphs, Deciding $k$-colorability of $P_5$-free graphs in polynomial time, Choosability of P 5-Free Graphs, A complexity dichotomy and a new boundary class for the dominating set problem, Unnamed Item, 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, Partitioning $H$-free graphs of bounded diameter, On line graphs of subcubic triangle-free graphs, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Boundary classes for graph problems involving non-local properties, Colouring diamond-free graphs, On the complexity of colouring antiprismatic graphs, Regular pattern-free coloring, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs, 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, Colouring square-free graphs without long induced paths., On the complexity of cd-coloring of graphs, Reducing the chromatic number by vertex or edge deletions, Colouring $(P_r + P_s)$-free graphs, On the chromatic number of ($P_6$, diamond)-free graphs, Solving the clique cover problem on (bull, $C_4$)-free graphs, Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, Contraction Blockers for Graphs with Forbidden Induced Paths, Colouring of graphs with Ramsey-type forbidden subgraphs, Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes, A coloring algorithm for $4 K_1$-free line graphs, 3-colouring AT-free graphs in polynomial time, A decidability result for the dominating set problem, Towards an isomorphism dichotomy for hereditary graph classes, Determining the chromatic number of triangle-free $2P_3$-free graphs in polynomial time, On Betti numbers of flag complexes with forbidden induced subgraphs, Non-empty intersection of longest paths in $H$-free graphs, 3-colouring $P_t$-free graphs without short odd cycles, Colouring of $(P_3 \cup P_2)$-free graphs, On colouring $(2P_2,H)$-free and $(P_5,H)$-free graphs, \textsc{max-cut} and containment relations in graphs, Coloring graphs without short cycles and long induced paths, On the parameterized complexity of coloring graphs in the absence of a linear forest, Better 3-coloring algorithms: excluding a triangle and a seven vertex path, 3-colorability $\in \mathcal P$ for $P_{6}$-free graphs., Coloring graphs characterized by a forbidden subgraph, Critical vertices and edges in $H$-free graphs, The coloring problem for classes with two small obstructions, The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs, Polynomial cases for the vertex coloring problem, List $k$-colouring $P_t$-free graphs: a mim-width perspective, Independent feedback vertex set for $P_5$-free graphs, Classifying $k$-edge colouring for $H$-free graphs, Improved complexity results on $k$-coloring $P_t$-free graphs, 3-Colorable Subclasses of $P_8$-Free Graphs, Two complexity results for the vertex coloring problem, On the algorithmic aspects of strong subcoloring, The computational complexity of weighted vertex coloring for $\{P_5,K_{2,3},K^+_{2,3}\}$-free graphs, 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, Some new hereditary classes where graph coloring remains NP-hard, A Note on k-Colorability of P 5-Free Graphs, Stable sets in $k$-colorable $P_{5}$-free graphs, 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, 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, Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size, Coloring Graphs without Short Cycles and Long Induced Paths, Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes, Colouring (P_r+P_s)-Free Graphs, Colouring H-free graphs of bounded diameter., Open Problems on Graph Coloring for Special Graph Classes, $(2P_2,K_4)$-Free Graphs are 4-Colorable, 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, Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions, $H$-colouring $P_t$-free graphs in subexponential time, Colouring square-free graphs without long induced paths, Connected greedy coloring of $H$-free graphs, Efficient approximation for restricted biclique cover problems, On coloring a class of claw-free and hole-twin-free graphs, Revising Johnson's table for the 21st century, 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, Injective colouring for H-free graphs, A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs