Partitioning graphs with linear minimum degree

MaRDI QIDQ6440235zbMATH OpenFDO

Authors Jie Ma, Hehui Wu

Publication date 13 June 2023

Abstract: We prove that there exists an absolute constant $C>0$ such that, for any positive integer $k$, every graph $G$ with minimum degree at least $Ck$ admits a vertex-partition $V(G)=ScupT$, where both $G[S]$ and $G[T]$ have minimum degree at least $k$, and every vertex in $S$ has at least $k$ neighbors in $T$. This confirms a question posted by K"uhn and Osthus and is tight up to a constant factor. Our proof combines probabilistic methods with structural arguments based on Ore's Theorem on $f$-factors of bipartite graphs.

This page was built for publication: Partitioning graphs with linear minimum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6440235)