On planar perfectly contractile graphs
type: Item
instance of: scholarly article
title: On planar perfectly contractile graphs
zbMATH Open document ID: 0872.05038
DOI: 10.1007/BF03352994
author: Frédéric Maffray
author: Cláudia L. Sales
author: Bruce Reed
published in: Graphs and Combinatorics
publication date: 1997-09-19T00:00:00Z
review text: Two non-adjacent vertices of a graph \(G\) are called an even pair if every induced path between them has an even number of edges. A graph \(G\) is called perfectly contractile if, for all induced subgraphs \(H\) of \(G\), there exists a sequence of graphs \(H=H_0, H_1,\ldots, H_k\) such that \(H_{i+1}\) arises from \(H_i\) by contracting one even pair, and \(H_k\) is a complete graph. An odd stretcher is a graph obtained from the complement of a chordless cycle with 6 vertices by subdividing the three edges that do not belong to a triangle in such a way that each of the three subdivided paths has an odd length. The authors prove that a planar graph is perfectly contractile if and only if it contains no (induced) cycle of odd length \(> 3\) and no odd stretcher. This result supports the following conjecture (due to H. Everett and B. A. Reed, 1993): A graph is perfectly contractile if and only if it contains no cycle of odd length \(> 3\), no complement of such a cycle, and no odd stretcher. The authors also give a polynomial-time algorithm for the recognition of perfectly contractile planar graphs. Their algorithm makes use of Hsu's decomposition of perfect planar graphs (see\textit{W.-L. Hsu} [Recognizing planar perfect graphs, J. Assoc. Comp. Mach. 34, No. 2, 255-288 (1987)]).
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1029267
zbMATH Keywords: perfect graphs
zbMATH Keywords: even pair
zbMATH Keywords: perfectly contractile graphs
zbMATH Keywords: planar graphs
MaRDI profile type: Publication
cites work: Perfectly contractile graphs
cites work: Transformations which Preserve Perfectness and H-Perfectness of Graphs
cites work: Perfectly orderable graphs are quasi-parity graphs: a short proof
cites work: Coloring planar perfect graphs by decomposition
cites work: A new property of critical imperfect graphs and some consequences
cites work: Planar graphs: Theory and algorithms
cites work: Q3680855
full work available at URL: https://doi.org/10.1007/bf03352994
OpenAlex ID: W1990396700
Recommended article: A class of perfectly contractile graphs
Recommended article: Contracting planar graphs to contractions of triangulations
Recommended article: Perfectly contractile graphs
Recommended article: On dart-free perfectly contractile graphs
Recommended article: Contractions of Planar Graphs in Polynomial Time
Recommended article: Perfectly contractile diamond-free graphs
Recommended article: Algorithms for Perfectly Contractile Graphs
Recommended article: On almost-planar graphs
Recommended article: On Contracting Graphs to Fixed Pattern Graphs
Recommended article: Contracting a Planar Graph Efficiently
description: scientific article; zbMATH DE number 1029267