2014/01/13 by Valentin Borozan, Borozan, Valentin, Michael Ferrara +11
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1401.2696
arxiv created 2015/07/27 · arxiv updated 2015/07/28
Given k≥ 1, a k-proper partition of a graph G is a partition \mathcal P of V(G) such that each part P of \mathcal P induces a k-connected subgraph of G. We prove that if G is a graph of order n such that δ(G)≥ √(n), then G has a 2-proper partition with at most n/δ(G) parts. The bounds on the number of parts and the minimum degree are both best possible. We then prove that If G is a graph of order n with minimum degree δ(G)≥√(c(k-1)n), where c=(2123)/(180), then G has a k-proper partition into at most (cn)/(δ(G)) parts. This improves a result of Ferrara, Magnant and Wenger [Conditions for Families of Disjoint k-connected Subgraphs in a Graph, Discrete Math. 313 (2013), 760--764] and both the degree condition and the number of parts are best possible up to the constant c.