Multicolour Turán problems
Multicolour Turán problems
复制标题
多色图兰问题
DOI：
10.1016/j.aam.2003.08.005
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Jacques Verstraëte
中科院分区：
文献类型：
--
作者：
Peter Keevash;M. Saks;B. Sudakov;Jacques Verstraëte
一个多重图G的简单k-染色是边集的分解为k个简单图的和，称为“颜色”。G中某个固定图H的一个副本称为多色的，如果它的边都有不同的颜色。回想一下，H的图兰数ex（n，H）是在n个顶点上的图中不包含H的副本的最大边数。我们考虑一个多色推广exk（n，H），定义为n个顶点上的多重图的最大边数，它具有一个简单的k-着色，不包含H的多色副本.这样一个重图的自然构造是H的一个固定极图的k个副本。我们证明了这对于足够大的k=k（n）是最优的，即，exk（n，H）=k·ex（n，H），而且只有这种构造才能实现等式。对于k e（H）−1，可以取k个完全图的拷贝，而不需要创建H的多色拷贝，所以这是最好的可能构造。即使对于k ∈ e（H），我们也应该考虑沿着这些路线的竞争构造，即完全图Kn的e（H）−1个副本。当H=Krand n很大时，最佳结构总是这两个之一，即， [公式：见正文]我们证明了3-色临界图的一个类似结果。我们也得到了一些关于二部图的部分结果。特别地，存在常数c<C，使得对于n的无穷多个值[公式：见正文]
A simple k-colouring of a multigraph G is a decomposition of the edge multiset as the sum of k simple graphs, called ‘colours’. A copy of some fixed graph H in G is called multicoloured if its edges all have distinct colours. Recall that the Turán number ex(n,H) of H is the maximum number of edges in a graph on n vertices not containing a copy of H. We consider a multicolour generalisation exk(n,H), defined as the maximum number of edges in a multigraph on n vertices, that has a simple k-colouring not containing a multicoloured copy of H. A natural construction of such a multigraph is k copies of a fixed extremal graph for H. We show that this is optimal for sufficiently large k=k(n), i.e., exk(n,H)=k·ex(n,H), and moreover only this construction achieves equality. For k⩽e(H)−1 one can take k copies of the complete graph without creating a multicoloured copy of H, so this is trivially the best possible construction. Even for k⩾e(H), we should consider a competing construction along these lines, namely e(H)−1 copies of the complete graph Kn. When H=Krand n is large, the optimal construction is always one of these two, i.e., [Formula: see text] We prove a similar result for 3-colour-critical graphs. We also have some partial results for bipartite graphs. In particular, there are constants c<C so that for infinitely many values of n [Formula: see text]