scientific article; zbMATH DE number 2044943

zbMATH Open1042.68639MaRDI QIDQ4448764FDOQ4448764

Daniel Král', Gerhard J. Woeginger, Zsolt Tuza, Jan Kratochvíl

Publication date: 18 February 2004

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2204/22040254.htm

Title of this publication is not available (Why is that?)

Recommendations

• Coloring graphs characterized by a forbidden subgraph
• Coloring graphs characterized by a forbidden subgraph
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Coloring graphs with forbidden induced subgraphs

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)

Cited In (only showing first 100 items - show all)

• Colouring of graphs with Ramsey-type forbidden subgraphs
• On the parameterized complexity of coloring graphs in the absence of a linear forest
• Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• Choosability of P 5-Free Graphs
• On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
• Complexity of total dominator coloring in graphs
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Vertex coloring of graphs with few obstructions
• Colouring vertices of triangle-free graphs without forests
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• The coloring problem for classes with two small obstructions
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Coloring graphs without short cycles and long induced paths
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Coloring Graphs without Short Cycles and Long Induced Paths
• Colouring H-free graphs of bounded diameter.
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Critical vertices and edges in \(H\)-free graphs
• Colouring of \((P_3 \cup P_2)\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• 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
• Solving the clique cover problem on (bull, \(C_4\))-free graphs
• A Note on k-Colorability of P 5-Free Graphs
• On coloring a class of claw-free graphs.
• Colouring \((P_r + P_s)\)-free graphs
• On the complexity of cd-coloring of graphs
• \textsc{max-cut} and containment relations in graphs
• List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
• 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
• Colouring square-free graphs without long induced paths
• 3-colouring AT-free graphs in polynomial time
• 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
• A complexity dichotomy and a new boundary class for the dominating set problem
• Title not available (Why is that?)
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Coloring graphs characterized by a forbidden subgraph
• List coloring in the absence of two subgraphs
• List Coloring in the Absence of a Linear Forest
• Complexity of coloring graphs without paths and cycles
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• A decidability result for the dominating set problem
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
• Connected greedy coloring of \(H\)-free graphs
• max-cut and Containment Relations in Graphs
• Some new hereditary classes where graph coloring remains NP-hard
• Open Problems on Graph Coloring for Special Graph Classes
• Colouring Vertices of Triangle-Free Graphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Two complexity results for the vertex coloring problem
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• Two cases of polynomial-time solvability for the coloring problem
• Algorithms for the rainbow vertex coloring problem on graph classes
• Polynomial cases for the vertex coloring problem
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
• $(2P_2,K_4)$-Free Graphs are 4-Colorable
• 4-Coloring H-Free Graphs When H Is Small
• Graph clustering via generalized colorings
• Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem
• Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Bisimplicial separators
• Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
• The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs
• Efficient approximation for restricted biclique cover problems
• The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
• Independent feedback vertex set for \(P_5\)-free graphs
• Injective colouring for H-free graphs
• Approximately coloring graphs without long induced paths
• Domination, coloring and stability in \(P_5\)-reducible graphs
• On Betti numbers of flag complexes with forbidden induced subgraphs
• Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs
• Graphs with at most two moplexes
• Colouring square-free graphs without long induced paths.
• On the chromatic number of (\(P_6\), diamond)-free graphs
• Reducing the chromatic number by vertex or edge deletions
• On the algorithmic aspects of strong subcoloring
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Contraction Blockers for Graphs with Forbidden Induced Paths
• 3-Colorable Subclasses of $P_8$-Free Graphs
• On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Colouring (P_r+P_s)-Free Graphs
• On the complexity of colouring antiprismatic graphs
• Partitioning \(H\)-free graphs of bounded diameter

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4448764)