论文标题
$ k_4 $ free Graphs的稀疏半份
Sparse halves in $K_4$-free graphs
论文作者
论文摘要
Chung和Graham的猜想指出，$ n $ Vertices上的每个$ k_4 $ free Graph都包含一组尺寸$ \ lfloor n/2 \ rfloor $，最多涵盖$ n^2/18 $边缘。我们通过证明它为所有常规图所保留的第一步迈出了这一猜想。
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.
