Coloring graphs characterized by a forbidden subgraph

DOI10.1016/j.dam.2014.08.008zbMath1303.05061OpenAlexW2026189561MaRDI QIDQ476308

Daniël Paulusma, Petr A. Golovach, 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

zbMATH Keywords

algorithmscomputational complexitygraph coloringforbidden subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (10)

An intractability result for the vertex 3-colourability problem ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ 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 ⋮ Two complexity results for the vertex coloring problem ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Quickly excluding a forest
• Some simplified NP-complete graph problems
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 4-coloring \(H\)-free graphs when \(H\) is small
• Vertex colouring and forbidden subgraphs -- a survey
• Hard coloring problems in low degree planar bipartite graphs
• Improved Complexity Results on k-Coloring P t -Free Graphs
• Graph colorings with local constraints -- a survey
• Independent Set in P₅-Free Graphs in Polynomial Time

This page was built for publication: Coloring graphs characterized by a forbidden subgraph