Coloring vertices of a graph or finding a Meyniel obstruction

Simple item page
dc.creatorCameron, Kathie
dc.creatorEdmonds, Jack
dc.creatorLévêque, Benjamin
dc.creatorMaffray, Frédéric
dc.date2005-09-08
dc.date2007-11-13
dc.date.accessioned2026-07-07T08:42:26Z
dc.date.available2026-07-07T08:42:26Z
dc.descriptionA 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.
dc.identifierhttps://arxiv.org/abs/cs/0509023
dc.identifierhttp://arxiv.org/abs/cs/0509023
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/141956
dc.subjectDiscrete Mathematics
dc.titleColoring vertices of a graph or finding a Meyniel obstruction
dc.typetext

Files

Collections

arXiv