Repeated Patterns in Proper Colorings
Repeated Patterns in Proper Colorings
复制标题
DOI：
10.1137/21m1414103
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
D. Conlon;Mykhaylo Tyomkyn
中科院分区：
文献类型：
--
作者：
D. Conlon;Mykhaylo Tyomkyn
对于一个固定图H，有C色的完全图K_n的正确边染色不包含H的两个点不相交的颜色同构的副本或重复，C的最小色数C是什么？我们使用各种组合、概率和代数技术研究这个函数及其推广到两个以上的副本。例如，我们证明了对于任意树T，存在一个常数c，使得K_n的任一色至多为Cn的正常边染色包含T的两个重复，而对于某个绝对常数c‘，存在至少有C’n^(3/2)个色的染色，它不包含任何至少有两条边的树的三个重复。我们还证明了对任何含有圈的图H，都存在k和c，使得K_n有一个正常的边染色，至多Cn个色不包含H的k个重复，而对于m个边的树T，有o(n^((m+1)/m))个色的染色包含T的ω(1)个重复。
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 cn² colours contains two repeats of T, while there are colourings with at least 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 cn 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.