Partitioning a Graph into Highly Connected Subgraphs. Issue 3 (17th August 2015) - Borozan, Valentin; Ferrara, Michael; Fujita, Shinya; Furuya, Michitaka; Manoussakis, Yannis; N, Narayanan; Stolee, Derrick
Abstract: Given k ≥ 1, a k ‐ proper partition of a graph G is a partition P of V ( G ) such that each part P of 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 c n δ ( G ) parts. This improves a result of Ferrara et al. ( Discrete Math 313 (2013), 760–764), and both the degree condition and the number of parts is best possible up to the constant c .