<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Contractible Triples in Highly Connected Graphs
Shinya Fujita1 and Ken-ichi Kawarabayashi2
1Department of Mathematics, Gunma National College of Technology, 580 Toriba, Maebashi, Gunma 371-8530, Japan
fujita@nat.gunma-ct.ac.jp
2National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
k\_keniti@nii.ac.jp
Annals of Combinatorics 14 (4) pp.457-465 December, 2010
AMS Subject Classification: 05C40, 05C75
Abstract:
We prove that if G is k-connected (with k ≥ 2), then G contains either a cycle of length 4 or a connected subgraph of order 3 whose contraction results in a k-connected graph. This immediately implies that any k-connected graph has either a cycle of length 4 or a connected subgraph of order 3 whose deletion results in a (k-1)-connected graph.
Keywords: contractible triples, highly connected graph

References:

1. Egawa, Y.: Contractible cycles in graphs with girth at least 5. J. Combin. Theory Ser. B 74(2), 213--264 (1998)

2. Kawarabayashi, K.: Contractible edges and triangles in k-connected graphs. J. Combin. Theory Ser. B 85(2), 207--221 (2002)

3. Kriesell, M.: Contractible subgraphs in 3-connected graphs. J. Combin. Theory Ser. B 80(1), 32--48 (2000)

4. McCuaing, W., Ota, K.: Contractible triples in 3-connected graphs. J. Combin. Theory Ser. B 60(2), 308--314 (1994)

5. Thomassen, C.: Nonseparating cycles in k-connected graphs. J. Graph Theory 5(4), 351--354 (1981)

6. Tutte, W.T.: How to draw a graph. Proc. London Math. Soc. (3) 13, 743--767 (1963)