2024/03/13 by Michitaka Furuya, Furuya, Michitaka, Masaki Kashima +3
Computer Science · #05C07 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2403.08465
openalex publication_date 2024/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A vertex partition in which every part induces a 2-connected subgraph is called a 2-proper partition. This concept was introduced by Ferrara et al. in 2013, and Borozan et al. gave the best possible minimum degree condition for the existence of a 2-proper partition in 2016. Later, in 2022, Chen et al. extended the result by showing a minimum degree sum condition for the existence of 2-proper partition. In this paper, we introduce two new invariants of graph, denoted by σ^*(G) and α^*(G). These two invariants are defined from degree sum on all independent sets with some property. We prove that if a graph G satisfies σ^*(G)≥ |V(G)|, then with some exceptions, G has a 2-proper partition with at most α^*(G) parts. This result is best possible, and implies both of the results by Borozan et al. and by Chen et al.. Moreover, as a corollary of our result, we give a minimum degree product condition for the existence of a 2-proper partition.