Originator: Carsten Thomassen (presented by Kyle Jao - REGS 2008)
Definitions:
Let f(s,t) be the smallest number such that the vertex set of every
graph with connectivity at least f(s,t) can be partitioned into two
sets that induce subgraphs with connectivity at least s and t,
respectively. That is, if a graph G is f(s,t)-connected, then
there is a partition (S,T) of V(G) such that G[S] is
s-connected and G[T] is t-connected.
Similarly,
let g(s,t) be the smallest number such that the vertex set of every
graph with minimum degree at least g(s,t) can be partitioned into two
sets that induce subgraphs with minimum degree at least s and t,
respectively.
Background: Thomassen [T1] and M. Szegedy (unpub) independently proved that f(s,t) exists. Thomassen also that g(s,t) exists.
Conjecture: f(s,t)=s+t+1 for s,t≥0.
Comments: Thomassen also conjectured that g(s,t)=s+t+1, which was proved by M. Stiebitz [S]. The complete graph Ks+t+1 shows that f(s,t)≥s+t+1. The statement holds when min{s,t}≤1 by the definition of connectivity. Thomassen [T2] proved the conjecture when min{s,t}=2 by finding a nonseparating cycle whose deletion reduces the connectivity by at most 3.
P. Hajnal [H] proved that f(s,t)≤4s+4t-13 for s,t≥3 using a theorem of Mader [M] and the proof of a theorem in [T1] that if a graph G with connectivity at least s+t-1 contains two vertex disjoint subgraphs with connectivity at least s and t, then there is a parition (S,T) of V(G) such that G[S] is s-connected and G[T] is t-connected.
Mader [M] proved that 2k-2≤h(k)≤4k-6 for k≥2, where h(k) is the smallest number such that every graph with minimum degree at least h(k) contains a k-connected subgraph. Results of Stiebitz, Mader, and Thomassen together imply f(s,t)≤h(s)+h(t)+1. An improvement of the upper bound for h(k) would yield an improvement of the upper bound for f(s,t). There are analogous conjectures for other parameters. For example Erdős and Lovász conjectured in 1968 that for every graph G with χ(G)>ω(G) and s+t=χ(G)+1 with s,t≥2, there is a partition of the vertex set into two sets with chromatic numbers at least s and t. Kostochka and Stiebitz [KS] proved this conjecture for line graphs of multigraphs.
References:
[H] P. Hajnal, Partition of graphs with condition on the connectivity and
minimum degree, Combinatorica 3 (1983), 95-99.
[KS A. Kostochka and M. Stiebitz, Partitions and edge colourings of multigraphs,
Electr. J. Combin. 15 (2008), Note N25, 4 pages.
[M] W. Mader, Existenz n-fach zusammenhängender Teilgraphen in
Graphen genügend grosser Kantendichte,
(German) Abh. Math. Sem. Hamburg Univ. 37 (1972), 86-97.
[S] M. Stiebitz, Decomposing graphs under degree constraints, J. Graph Theory
23 (1996), 321-324.
[T1] C. Thomassen, Graph decomposition with constraints on the connectivity and
minimum degree, J. Graph Theory 7 (1983), 165-167.
[T2] C. Thomassen, Nonseparating cycles in k-connected graphs,
J. Graph Theory 5 (1981), 351--354.
Updated July 28, 2008