2010/10/11 by Etienne Fieux, Fieux, Etienne, Jacqueline Lacaze +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1010.2047
15 pages, 10 figures, partially presented at the 8th French Combinatorial Conference (0rsay, 2010, 28 June - 2 July)
arxiv created 2010/10/11 · arxiv updated 2010/10/12
We study dismantlability in graphs. In order to compare this notion to similar operations in posets (partially ordered sets) or in simplicial complexes, we prove that a graph G dismants on a subgraph H if and only if H is a strong deformation retract of G. Then, by looking at a triangle relating graphs, posets and simplicial complexes, we get a precise correspondence of the various notions of dismantlability in each framework. As an application, we study the link between the graph of morphisms from a graph G to a graph H and the polyhedral complex Hom(G,H); this gives a more precise statement about well known results concerning the polyhedral complex Hom(G,H) and its relation with foldings in G or H.