首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Slightly triangulated graphs are perfect
Authors:Frédéric Maire
Institution: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;
  1. G contains no chordless cycle with at least 5 vertices.
  2. 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号