Coloring vertices of a graph or finding a Meyniel obstruction
<|reference_start|>Coloring vertices of a graph or finding a Meyniel obstruction: 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. Here we give a O(n^2) algorithm that, for any graph, finds either a clique and coloring of the same size or a Meyniel obstruction. We also give a O(n^3) algorithm that, for any graph, finds either aneasily recognizable strong stable set or a Meyniel obstruction.<|reference_end|>
@article{cameron2005coloring,
    title={Coloring vertices of a graph or finding a Meyniel obstruction},
    author={Kathie Cameron (WLU), Jack Edmonds (EP INSTITUTE), Benjamin
  L'ev^eque (LGS), Fr'ed'eric Maffray (LGS)},
    journal={arXiv preprint arXiv:cs/0509023},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0509023},
    primaryClass={cs.DM}
}