A class of perfectly contractile graphs

DOI10.1016/j.jctb.2005.06.011zbMath1078.05034arXiv1309.0438OpenAlexW3105460076MaRDI QIDQ2581496

Nicolas Trotignon, Frédéric Maffray

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

AlgorithmPerfect graphColoringEven pair

Mathematics Subject Classification ID

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

Related Items (10)

Even pairs in square-free Berge graphs ⋮ Perfectly contractile graphs and quadratic toric rings ⋮ Stability preserving transformations of graphs ⋮ Coloring square-free Berge graphs ⋮ On Roussel-Rubio-type lemmas and their consequences ⋮ Graph transformations preserving the stability number ⋮ Graph transformations preserving the stability number ⋮ Precoloring extension of co-Meyniel graphs ⋮ Even pairs in Berge graphs ⋮ Coloring Artemis graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weakly triangulated graphs
• Perfectly contractile graphs
• The strong perfect graph theorem
• On the complexity of recognizing perfectly orderable graphs
• Perfectly orderable graphs are quasi-parity graphs: a short proof
• A new property of critical imperfect graphs and some consequences
• A fast algorithm for coloring Meyniel graphs
• On planar perfectly contractile graphs
• Optimizing weakly triangulated graphs
• About skew partitions in minimal imperfect graphs
• Even pairs in Artemis graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs

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