RETRACT-COLLAPSIBLE GRAPHS AND INVARIANT SUBGRAPH PROPERTIES

A (finite or infinite) graph G is retract-collapsible if it can be dis mantled by deleting systematically at each step every vertex that is s trictly dominated, in such a way that the remaining subgraph is a retr act of G, and so as to get a simplex at the end. A graph is subretract -collapsible if some graph obtained by planting some rayless tree at e ach of its vertices is retract-collapsible. It is shown that the subre tract-collapsible graphs are cop-win; and that a ball-Helly graph is s ubretract-collapsible if and only if it has no isometric infinite path s (thus in particular if it has no infinite paths, or if it is bounded ). Several fixed subgraph properties are proved. In particular, if G i s a subretract-collapsible graph, and f a contraction from G into G, t hen (i) if G has no infinite simplices, then f(S) = S for some simplex S of G; and (ii) if the dismantling of G can be achieved in a finite number of steps and if some family of simplices of G has a compacity p roperty, then there is a simplex S of G such that f(S) subset-or-equal -to S. This last result generalizes a property of bounded ball-Helly g raphs. (C) 1995 John Wiley & Sons, Inc.