Slightly triangulated graphs are perfect |
| |
Authors: | Frédéric Maire |
| |
Affiliation: | 1. Case 189 Equipe Combinatoire Université, Paris 6, France
|
| |
Abstract: | A graph istriangulated if it has no chordless cycle with at least four vertices (?k ≥ 4,C k ?G). These graphs Jhave been generalized by R. Hayward with theweakly triangulated graphs $(forall k geqslant 5,C_{k,} bar C_k nsubseteq G)$ . In this note we propose a new generalization of triangulated graphs. A graph G isslightly triangulated if it satisfies the two following conditions; - G contains no chordless cycle with at least 5 vertices.
- For every induced subgraphH of G, there is a vertex inH the neighbourhood of which inH contains no chordless path of 4 vertices.
|
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|