Contractible elements in k-connected graphs not containing some specified graphs

摘要

In [15], Thomassen proved that any triangle-free k-connected graph has a contractible edge. Starting with this result, there are several results concerning the existence of contractible elements in k-connected graphs which do not contain specified subgraphs. These results extend Thomassen's result, cf., [2,3,9-12]. In particular, Kawarabayashi [12] proved that any k-connected graph without K-4(-) subgraphs contains either a contractible edge or a contractible triangle. In this article, we further extend these results, and prove the following result. Let k be an integer with k >= 6. If G is a k-connected graph such that G does not contain D-1 = K-1 + (K-2 boolean OR P-3) as a subgraph and G does not contain D-2 = K-2 + (k - 2)K-1 as an induced subgraph, then G has either a contractible edge which is not contained in any triangle or a contractible triangle. (C) 2008 Wiley Periodicals, Inc.