A class of perfectly contractile graphs

DOI10.1016/J.JCTB.2005.06.011MaRDI QIDQ2581496zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray, Nicolas Trotignon

Publication date 10 January 2006

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.0438

zbMATH Keywords

AlgorithmColoringPerfect graphEven pair

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Abstract: We consider the class $calA$ 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 $GincalA$ 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 $calA$. This entails a polynomial-time algorithm, based on successively contracting even pairs, to color optimally every graph in $calA$. This generalizes several results concerning some classical families of perfect graphs.

Recommendations

• Algorithms for Perfectly Contractile Graphs
• Path parity and perfection
• Perfectly contractile diamond-free graphs
• Even pairs in claw-free perfect graphs
• On planar perfectly contractile graphs

Cites work

• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• scientific article; zbMATH DE number 2096444 (Why is no real title available?)
• A fast algorithm for coloring Meyniel graphs
• A new property of critical imperfect graphs and some consequences
• About skew partitions in minimal imperfect graphs
• Even pairs
• Even pairs in Artemis graphs
• On planar perfectly contractile graphs
• On the complexity of recognizing perfectly orderable graphs
• Optimizing weakly triangulated graphs
• Perfectly contractile graphs
• Perfectly orderable graphs are quasi-parity graphs: a short proof
• The strong perfect graph theorem
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• Weakly triangulated graphs

Cited in

(21)

• On planar perfectly contractile graphs
• On Roussel-Rubio-type lemmas and their consequences
• Coloring square-free Berge graphs
• Graph transformations preserving the stability number
• On dart-free perfectly contractile graphs
• Even pairs in Berge graphs with no balanced skew-partitions
• Even pairs in Berge graphs
• Precoloring extension of co-Meyniel graphs
• Stability preserving transformations of graphs
• Coloring Artemis graphs
• Even pairs in square-free Berge graphs
• On the complexity of colouring antiprismatic graphs
• Algorithms for Perfectly Contractile Graphs
• Graph transformations preserving the stability number
• Perfectly contractile graphs
• Even pairs
• Perfectly contractile diamond-free graphs
• Perfectly contractile graphs and quadratic toric rings
• scientific article; zbMATH DE number 4120196 (Why is no real title available?)
• scientific article; zbMATH DE number 1512683 (Why is no real title available?)
• Contractions in perfect graphs

This page was built for publication: A class of perfectly contractile graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581496)