Coloring vertices of a graph or finding a Meyniel obstruction

DOI10.1016/j.tcs.2011.12.018zbMath1242.05088OpenAlexW2069229408MaRDI QIDQ418741

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

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

perfect graphscoloringMeyniel graphsexistentially polytime theoremstrong stable set

Mathematics Subject Classification ID

Paths and cycles (05C38) 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)

Structure and algorithms for (cap, even hole)-free graphs

Cites Work

• The strong perfect graph theorem
• On a conjecture of Meyniel
• A fast algorithm for coloring Meyniel graphs
• On the perfect graph conjecture
• Recognizing Berge graphs
• HOLES AND DOMINOES IN MEYNIEL GRAPHS
• An \(O(n^2)\) algorithm to color Meyniel graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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