2024/07/20 by Li, Xihe, Ma, Jie, Zheng, Zhiheng · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.14905
A \it simple k-coloring of a multigraph G is a decomposition of the edge multiset as a disjoint sum of k simple graphs which are referred as colors. A subgraph H of a multigraph G is called \it multicolored if its edges receive distinct colors in a given simple k-coloring of G. In 2004, Keevash-Saks-Sudakov-Verstraëte introduced the \it k-color Turán number exk(n,H), which denotes the maximum number of edges in an n-vertex multigraph that has a simple k-coloring containing no multicolored copies of H. They made a conjecture for any r≥ 3 and r-color-critical graph H that in the range of k≥ (r-1)/(r-2)(e(H)-1), if n is sufficiently large, then exk(n, H) is achieved by the multigraph consisting of k colors all of which are identical copies of the Turán graph Tr-1(n). In this paper, we show that this holds in the range of k≥ 2(r-1)/(r)(e(H)-1), significantly improving earlier results. Our proof combines the stability argument of Chakraborti-Kim-Lee-Liu-Seo with a novel graph packing technique for embedding multigraphs.