Coloring vertices of a graph or finding a Meyniel obstruction

DOI10.1016/J.TCS.2011.12.018zbMATH Open1242.05088OpenAlexW2069229408MaRDI QIDQ418741FDOQ418741

Authors: Kathie Cameron, Benjamin Lévêque, Frédéric Maffray 

Publication date: 30 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.018

Recommendations

• Finding a strong stable set or a Meyniel obstruction in any graph
• Coloring Meyniel graphs in linear time
• A fast algorithm for coloring Meyniel graphs
• An \(O(n^2)\) algorithm to color Meyniel graphs
• Recognition of quasi-Meyniel graphs

zbMATH Keywords

coloringperfect graphsexistentially polytime theoremMeyniel graphsstrong stable set

Mathematics Subject Classification ID

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

Cites Work

• The strong perfect graph theorem
• Recognizing Berge graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a conjecture of Meyniel
• A fast algorithm for coloring Meyniel graphs
• On the perfect graph conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding a strong stable set or a Meyniel obstruction in any graph
• Title not available (Why is that?)
• Holes and dominoes in Meyniel graphs
• An \(O(n^2)\) algorithm to color Meyniel graphs

Cited In (2)

• Structure and algorithms for (cap, even hole)-free graphs
• Finding a strong stable set or a Meyniel obstruction in any graph

This page was built for publication: Coloring vertices of a graph or finding a Meyniel obstruction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418741)