Sparse halves in $K_4$-free graphs

Abstract

A conjecture of Chung and Graham states that every $K_4$-free graph on $n$ vertices contains a vertex set of size $\lfloor n/2\rfloor$ that spans at most $n^2/18$ edges. We make the first step toward this conjecture by showing that it holds for all regular graphs.

19 pages including 3 pages appendix

References in corpus (1)

• On the local density problem for graphs of given odd-girth