A retraction problem in graph theory (Q1073052)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A retraction problem in graph theory |
scientific article |
Statements
A retraction problem in graph theory (English)
0 references
1985
0 references
A retraction from a graph G to an induced subgraph H is a mapping r: V(G)\(\to V(H)\) such that \(r(h)=h\) for all vertices h of H, and such that any adjacent vertices g, g' of G have images r(g), r(g') which are equal or adjacent in H. Graph retractions (just as retractions in any other category) are related to extendability of homomorphisms, and were studied by Sabidussi, Rival, Nowakowski, Bandelt, Pesch, the reviewer, and others. In particular, several authors (including the present author) obtained simple necessary and sufficient conditions on the existence of a retraction \(r: G\to H\) when H satisfies some special property (e.g. when H is a tree, or, more generally, when the closed k-neighborhoods in H have the Helly property). This paper uses homotopy techniques to prove that a finite planar graph G admits a retraction onto a chordless cycle H if and only if H is not the (mod-2) edge sum of shorter cycles. This is false when G is allowed to be non-planar. As an application, the author derives a theorem of Duchet, LasVergnas, and Meyniel.
0 references
homomorphism
0 references
Graph retractions
0 references
planar graph
0 references
chordless cycle
0 references