On the multicolor Turán conjecture for color-critical graphs
Xihe Li, Jie Ma, Zhiheng Zheng · Canadian Journal of Mathematics · 2025
Abstract A 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 to as colors. A subgraph H of a multigraph G is called multicolored if its edges receive distinct colors in a given simple k -coloring of G . In 2004, Keevash–Saks–Sudakov–Verstraëte introduced the k-color Turán number ${\text {ex}}_k(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\geq 3$ and r -color-critical graph $H,$ that in the range of $k\geq \frac {r-1}{r-2}(e(H)-1)$ , if n is sufficiently large, then ${\text {ex}}_k(n, H)$ is achieved by the multigraph consisting of k colors all of which are identical copies of the Turán graph $T_{r-1}(n)$ . In this article, we show that this holds in the range of $k\geq 2\frac {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.