<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume9 Issue1" %>
Non-Separating Paths in 4-Connected Graphs
Ken-ichi Kawarabayashi1, Orlando Lee2, and Xingxing Yu3,4
1Mathematics Department, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544, USA
2Instituto de Computac¸ ão, Universidade Estadual de Campinas, Caixa Postal 6176, 13083–971 Campinas - SP, Brazil
3School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332, USA
4Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, P.R. China
Annals of Combinatorics 9 (1) p.47-56 March, 2005
AMS Subject Classification: 05C38, 05C40
In 1975, Lovász conjectured that for any positive integer k, there exists a minimum positive integer f (k) such that, for any two vertices x; y in any f (k)-connected graph G, there is a path P from x to y in G such that G-V(P) is k-connected. A result of Tutte implies f(1)=3. Recently, f (2) = 5 was shown by Chen et al. and, independently, by Kriesell. In this paper, we show that f (2) = 4 except for double wheels.
Keywords: non-separating path, 4-connected graph, Lovász conjecture


1. G. Chen, R. Gould, and X. Yu, Graph connectivity after path removal, Combinatorica, to appear.

2. J. Cheriyan and S.N. Maheshwari, Finding non-separating induced cycles and independent spanning trees in 4-connected graphs, J. Algorithms 9 (1988) 507--537.

3. S. Curran and X. Yu, Nonseparating cycles in 4-connected graphs, SIAM J. Discrete Math. 16 (2003) 616--629.

4. M. Fontet, Graphes 4-essential, C. R. Acad. Sci. Paris 287 (1978) 289--290.

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

6. M. Kriesell, Induced paths in 5-connected graphs, J. Graph Theory 36 (2001) 52--58.

7. L. Lovász, Problems in Recent Advances in Graph Theory, M. Fiedler, Ed., Academia, Prague, 1975.

8. N. Martinov, Uncontractible 4-connected graphs, J. Graph Theory 6 (1982) 343--344.

9. P.D. Seymour, Disjoint paths in graphs, Discrete Math. 29 (1980) 293--309.

10. C. Thomassen, 2-Linked graphs, Europ. J. Combin. 1 (1980) 371--378.

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

12. C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169--176.

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