An \(O(n^2)\) algorithm to color Meyniel graphs

DOI10.1016/S0012-365X(00)00264-8zbMath0978.05033DBLPjournals/dm/RousselR01OpenAlexW2058694911WikidataQ56430116 ScholiaQ56430116MaRDI QIDQ5937923

Irena Rusu, F. Roussel

Publication date: 23 October 2001

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(00)00264-8

zbMATH Keywords

greedy algorithmperfect graphscoloringMeyniel graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Related Items (7)

Structure and algorithms for (cap, even hole)-free graphs ⋮ Coloring vertices of a graph or finding a Meyniel obstruction ⋮ Classes of perfect graphs ⋮ A new characterization of HH-free graphs ⋮ Coloring Artemis graphs ⋮ Coloring Meyniel graphs in linear time ⋮ Colouring Some Classes of Perfect Graphs Robustly

This page was built for publication: An \(O(n^2)\) algorithm to color Meyniel graphs