Coloring graphs characterized by a forbidden subgraph
DOI10.1016/J.DAM.2014.08.008zbMATH Open1303.05061OpenAlexW2026189561MaRDI QIDQ476308FDOQ476308
Authors: Petr A. Golovach, Daniël Paulusma, Bernard Ries 
Publication date: 28 November 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.08.008
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- 4-coloring \(H\)-free graphs when \(H\) is small
- Title not available (Why is that?)
- Title not available (Why is that?)
- Independent set in \(P_5\)-free graphs in polynomial time
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- The strong perfect graph theorem
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Some simplified NP-complete graph problems
- Graph colorings with local constraints -- a survey
- Quickly excluding a forest
- Title not available (Why is that?)
- Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
- Vertex colouring and forbidden subgraphs -- a survey
- Coloring edges and vertices of graphs without short or long cycles
- Hard coloring problems in low degree planar bipartite graphs
Cited In (32)
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Subdivision of the hierarchy of H-colorable graph classes by circulant graphs
- Title not available (Why is that?)
- Coloring graphs characterized by a forbidden subgraph
- Colouring vertices of triangle-free graphs without forests
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
- A new kind of graph coloring
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Title not available (Why is that?)
- On the algorithmic aspects of strong subcoloring
- On subgraphs without large components.
- Title not available (Why is that?)
- An intractability result for the vertex 3-colourability problem
- 4-coloring \(H\)-free graphs when \(H\) is small
- Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult
- 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
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- Colouring vertices of triangle-free graphs
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- A complexity dichotomy and a new boundary class for the dominating set problem
- Colorings of oriented planar graphs avoiding a monochromatic subgraph
- Regular pattern-free coloring
- Forbidden subgraphs of coloring graphs
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Two complexity results for the vertex coloring problem
- Coloring graphs with forbidden induced subgraphs
- On the girth of forbidden subgraphs of coloring graphs
- Title not available (Why is that?)
This page was built for publication: Coloring graphs characterized by a forbidden subgraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476308)
