2020/07/29 by Liu, Xizhi, Ma, Jie
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2007.14623
A conjecture of Chung and Graham states that every K4-free graph on n vertices contains a vertex set of size \lfloor n/2 \rfloor that spans at most n2/18 edges. We make the first step toward this conjecture by showing that it holds for all regular graphs.