Meyniel graphs are strongly perfect |
| |
Authors: | G Ravindra |
| |
Affiliation: | Équipe de recherche 175, Combinatoire Université de Paris VI, Paris, France |
| |
Abstract: | ![]() Meyniel (Discrete Math.16 (1976), 339–342) proved that a graph is perfect whenever each of its odd cycles of length at least five has at least two chords. This result is strengthened by proving that every graph satisfying Meyniel's condition is strongly perfect (i.e., each of its induced subgraphs H contains a stable set which meets all the maximal cliques in H). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|