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
    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
    0 references
    homomorphism
    0 references
    Graph retractions
    0 references
    planar graph
    0 references
    chordless cycle
    0 references

    Identifiers