全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Mathematics  2013 

A class of perfectly contractile graphs

DOI: 10.1016/j.jctb.2005.06.011

Full-Text   Cite this paper   Add to My Lib

Abstract:

We consider the class ${\cal A}$ of graphs that contain no odd hole, no antihole, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between them). We prove that every graph $G\in{\cal A}$ different from a clique has an "even pair" (two vertices that are not joined by a chordless path of odd length), as conjectured by Everett and Reed [see the chapter "Even pairs" in the book {\it Perfect Graphs}, J.L. Ram\'{\i}rez-Alfons\'{\i}n and B.A. Reed, eds., Wiley Interscience, 2001]. Our proof is a polynomial-time algorithm that produces an even pair with the additional property that the contraction of this pair yields a graph in ${\cal A}$. This entails a polynomial-time algorithm, based on successively contracting even pairs, to color optimally every graph in ${\cal A}$. This generalizes several results concerning some classical families of perfect graphs.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133