论文标题
正确着色的重复图案
Repeated patterns in proper colourings
论文作者
论文摘要
对于固定图$ h $，最小数量的颜色$ c $是什么，以使完整的图形$ k_n $具有适当的边彩色，其中包含$ c $ colloce，其中含有两个vertex-disjoint colour-ismormorphic-iSomorphicer-iSomorphicer-iSomorphice opers或repoys $ h $？我们使用多种组合，概率和代数技术研究了该功能及其对两份副本的概括。例如，我们表明，对于任何树$ t $，存在一个常数$ c $，以使任何适当的$ k_n $的适当边缘颜色最多$ c n^2 $包含两个重复$ t $的重复，而最多有$ c'n^{3/2} $ colors的颜色，对于某些绝对常数$ c'$ copers of Bocal coltance of 3 copers coles coles coles coptery的$ c n^$ coble最多包含$ t $ colorthe $ c n $ c $。 We also show that for any graph $H$ containing a cycle there exist $k$ and $c$ such that there is a proper edge-colouring of $K_n$ with at most $c n$ colours containing no $k$ repeats of $H$, while, for a tree $T$ with $m$ edges, a colouring with $o(n^{(m+1)/m})$ colours contains $ω(1)$ repeats of $T$.
For a fixed graph $H$, what is the smallest number of colours $C$ such that there is a proper edge-colouring of the complete graph $K_n$ with $C$ colours containing no two vertex-disjoint colour-isomorphic copies, or repeats, of $H$? We study this function and its generalisation to more than two copies using a variety of combinatorial, probabilistic and algebraic techniques. For example, we show that for any tree $T$ there exists a constant $c$ such that any proper edge-colouring of $K_n$ with at most $c n^2$ colours contains two repeats of $T$, while there are colourings with at most $c' n^{3/2}$ colours for some absolute constant $c'$ containing no three repeats of any tree with at least two edges. We also show that for any graph $H$ containing a cycle there exist $k$ and $c$ such that there is a proper edge-colouring of $K_n$ with at most $c n$ colours containing no $k$ repeats of $H$, while, for a tree $T$ with $m$ edges, a colouring with $o(n^{(m+1)/m})$ colours contains $ω(1)$ repeats of $T$.
