Domination, coloring and stability in \(P_5\)-reducible graphs

DOI10.1016/j.dam.2014.10.013zbMath1408.05097OpenAlexW2081351314MaRDI QIDQ2341757

Frédéric Maffray, Jean-Luc Fouquet

Publication date: 28 April 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.10.013

zbMATH Keywords

stabilitydominationcoloring\(P_5\)-free

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Spectral properties of cographs andP₅-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
• Complete description of forbidden subgraphs in the structural domination problem
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Dominating cliques in \(P_ 5\)-free graphs
• Computing independent sets in graphs with large girth
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Threshold graphs and related topics
• Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
• A Note on k-Colorability of P 5-Free Graphs
• The NP-Completeness of Edge-Coloring
• Graph colorings with local constraints -- a survey
• Dominating sets with small clique covering number
• Difference graphs
• Dominating cliques in graphs

This page was built for publication: Domination, coloring and stability in \(P_5\)-reducible graphs