论文标题
本地平衡着色中的不可避免的图案
Unavoidable patterns in locally balanced colourings
论文作者
论文摘要
如果每个顶点至少具有$ \ varepsilon n $红色和$ \ varepsilon n $蓝色邻居，则必须包含哪些模式的两种颜色$ k_n $？在本文中，我们研究了这个问题及其多色变体。例如，我们表明，任何此类图都包含\ textit {交替的4-cycle}的$ t $ blow和$ t =ω（\ log n）$。
Which patterns must a two-colouring of $K_n$ contain if each vertex has at least $\varepsilon n$ red and $\varepsilon n$ blue neighbours? In this paper, we investigate this question and its multicolour variant. For instance, we show that any such graph contains a $t$-blow-up of an \textit{alternating 4-cycle} with $t = Ω(\log n)$.
