Coloring graphs characterized by a forbidden subgraph
From MaRDI portal
(Redirected from Publication:476308)
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)- 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
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- 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 survey on the computational complexity of coloring graphs with forbidden subgraphs
- A new kind of graph coloring
- scientific article; zbMATH DE number 7656024 (Why is no real title available?)
- On the algorithmic aspects of strong subcoloring
- On subgraphs without large components.
- An intractability result for the vertex 3-colourability problem
- scientific article; zbMATH DE number 2089219 (Why is no real title available?)
- 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
- A complexity dichotomy and a new boundary class for the dominating set problem
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- 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
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- Coloring graphs with forbidden induced subgraphs
- On the girth of forbidden subgraphs of coloring graphs
- scientific article; zbMATH DE number 2044932 (Why is no real title available?)
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)
