Coloring vertices of a graph or finding a Meyniel obstruction

DOI10.1016/J.TCS.2011.12.018MaRDI QIDQ418741zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

coloringexistentially polytime theoremMeyniel graphsperfect graphsstrong stable set

Mathematics Subject Classification ID

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

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

Cites work

• A fast algorithm for coloring Meyniel graphs
• An O(n^2) algorithm to color Meyniel graphs
• Finding a strong stable set or a Meyniel obstruction in any graph
• Holes and dominoes in Meyniel graphs
• scientific article; zbMATH DE number 3884201 (Why is no real title available?)
• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• scientific article; zbMATH DE number 3889583 (Why is no real title available?)
• scientific article; zbMATH DE number 4199652 (Why is no real title available?)
• scientific article; zbMATH DE number 3556145 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• On a conjecture of Meyniel
• On the perfect graph conjecture
• Recognizing Berge graphs
• The strong perfect graph theorem

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)