Partitioning a Graph into Highly Connected Subgraphs
Valentin Borozan, Michael J. Ferrara, Shinya Fujita, Michitaka Furuya, Yannis Manoussakis, N. Narayanan, Derrick Stolee · Journal of Graph Theory · 2015
Abstract Given , a k‐proper partition of a graph G is a partition of such that each part P of induces a k‐connected subgraph of G. We prove that if G is a graph of order n such that , then G has a 2‐proper partition with at most 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 urn:x-wiley:03649024:media:jgt21904:jgt21904-math-0007 where , then G has a k‐proper partition into at most 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.