A class of perfectly contractile graphs

We consider the class 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 ∈ A different from a clique has an “even pair” (two vertices that are not joined by a chordless p...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2006, Vol.96 (1), p.1-19
Main Authors: Maffray, Frédéric, Trotignon, Nicolas
Format: Article
Language:English
Subjects:
Algorithm
Coloring
Combinatorics
Computer Science
Discrete Mathematics
Even pair
Mathematics
Perfect graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the class 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 ∈ 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 [“Even pairs”, in: J.L. Ramírez-Alfonsín, B.A. Reed (eds.), Perfect Graphs, Wiley Interscience, New York, 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 A . This entails a polynomial-time algorithm, based on successively contracting even pairs, to color optimally every graph in A . This generalizes several results concerning some classical families of perfect graphs.
ISSN:0095-8956
1096-0902
DOI:10.1016/j.jctb.2005.06.011