Graph Partitions Under Average Degree Constraint

Abstract

In this paper, we prove that every graph with average degree at least $s+t+2$ has a vertex partition into two parts, such that one part has average degree at least $s$, and the other part has average degree at least $t$. This solves a conjecture of Csóka, Lo, Norin, Wu and Yepremyan.