Partitioning graphs with linear minimum degree
Jie Ma, Hehui Wu · Random Structures and Algorithms · 2024
Abstract We prove that there exists an absolute constant such that, for any positive integer , every graph with minimum degree at least admits a vertex‐partition , where both and have minimum degree at least , and every vertex in has at least neighbors in . This confirms a question posted by Kühn and Osthus (J. Comb. Theory Ser. B. 88 (2003), 29–43.) and is tight up to a constant factor. Our proof combines probabilistic methods with structural arguments based on Ore's theorem on ‐factors of bipartite graphs.