Coloring vertices of a graph or finding a Meyniel obstruction - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Theoretical Computer Science Année : 2012

Coloring vertices of a graph or finding a Meyniel obstruction

Kathie Cameron
  • Fonction : Auteur
  • PersonId : 830780
Benjamin Lévêque
Frédéric Maffray

Résumé

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 a coloring of the same size or a Meyniel obstruction. We also give a O ( n 3 ) algorithm that, for any graph, finds either a strong stable set recognizable in polynomial time or a Meyniel obstruction.

Dates et versions

lirmm-00736506 , version 1 (28-09-2012)

Identifiants

Citer

Kathie Cameron, Benjamin Lévêque, Frédéric Maffray. Coloring vertices of a graph or finding a Meyniel obstruction. Theoretical Computer Science, 2012, 428, pp.10-17. ⟨10.1016/j.tcs.2011.12.018⟩. ⟨lirmm-00736506⟩
113 Consultations
0 Téléchargements

Altmetric

Partager

More