Coloring vertices of a graph or finding a Meyniel obstruction

Kathie Cameron, Jack Edmonds, Benjamin Lévêque +1

A Meyniel obstruction is an odd cycle with at least five vertices and at most one chord. A graph is Meyniel if and only if it has no Meyniel obstruction as an induced subgraph. Her…