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


A semi-strong Perfect Graph theorem
Institution:Computer Science Department, McGill University, Montreal Quebec Canada
Abstract:Perfect Graphs were defined by Claude Berge in 1961. Since that time this class of graphs has been intensely studied. Much of the work has been directed towards proving Berge's Strong and Weak Perfect Graph Conjectures. L. Lovász finally demonstrated the Weak Perfect Graph Conjecture in 1972. Vaśek Chvátal, in 1982, proposed the Semi-Strong Perfect Graph Conjecture which falls between these two conjectures. This conjecture suggests that the perfection of a graph depends solely on the way that the chordless paths with three edges are distributed within the graph. This paper contains a proof of Chvátal's conjecture.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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