On connected partition with degree constraints (Q2666577)

Let \(s\) and \(t\) be nonnegative integers, and let \(f(s,t)\) be the smallest positive integer such that every \(f(s,t)\)-connected graph \(G\) has a partition \(\{S,T\}\) of \(V(G)\) such that \(G[S]\) is \(s\)-connected and \(G[T]\) is \(t\)-connected. \textit{C. Thomassen} [Selected topics in graph theory, Vol. 3, 97--131 (1988; Zbl 0659.05062)] conjectured that \(f(s,t)=s+t+1\) for all positive integers \(s\) and \(t\). The best known bound for \(f(s,t)\) is \(f(s,t) \le 4s+4t-13\) if \(s\ge 3\) and \(t\ge 2\) due to \textit{P. Hajnal} [Combinatorica 3, 95--99 (1983; Zbl 0529.05030)]. The authors improve \(f(s,t)\) to \(\lceil \frac{19(s-1)}{6}+\rceil+\lceil \frac{19(t-1)}{6}+\rceil+1\) if \(\min\{s,t\} \ge 3\). They also improve the upper bound \(g(s,t)\) for some special classes of graphs, where \(g(s,t)\) is the smallest integer such that every graph \(G\) with minimum degree \(g(s,t)\) has a partition \(\{S,T\}\) of \(V(G)\) such that \(G[S]\) has minimum degree at least \(s\) and \(G[T]\) has minimum degree at least \(t\).