Coloring graphs characterized by a forbidden subgraph
From MaRDI portal
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 5179133 (Why is no real title available?)
- 4-coloring \(H\)-free graphs when \(H\) is small
- Coloring edges and vertices of graphs without short or long cycles
- Graph colorings with local constraints -- a survey
- Hard coloring problems in low degree planar bipartite graphs
- Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
- Independent set in \(P_5\)-free graphs in polynomial time
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Quickly excluding a forest
- Some simplified NP-complete graph problems
- The strong perfect graph theorem
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Vertex colouring and forbidden subgraphs -- a survey
Cited in
(33)- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Colouring of graphs with Ramsey-type forbidden 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
- Coloring graphs characterized by a forbidden subgraph
- Coloring graphs with forbidden induced subgraphs
- scientific article; zbMATH DE number 2089219 (Why is no real title available?)
- A new kind of graph coloring
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- An intractability result for the vertex 3-colourability problem
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 2044932 (Why is no real title available?)
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- scientific article; zbMATH DE number 7656024 (Why is no real title available?)
- Forbidden subgraphs of coloring graphs
- On the girth of forbidden subgraphs of coloring graphs
- Regular pattern-free coloring
- 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
- 4-coloring \(H\)-free graphs when \(H\) is small
- Colouring vertices of triangle-free graphs without forests
- Subdivision of the hierarchy of H-colorable graph classes by circulant graphs
- On subgraphs without large components.
- A complexity dichotomy and a new boundary class for the dominating set problem
- Two complexity results for the vertex coloring problem
- Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- On the algorithmic aspects of strong subcoloring
- Colorings of oriented planar graphs avoiding a monochromatic subgraph
- The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
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)
