2025/03/25 by Hàn, Hiêp, Hoppen, Carlos, Müller, Nicolas Moro +1 · 1 citation
#05C35 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2503.19244
In this paper we show that for r≥ 12 and any sufficiently large n-vertex graph G the number of r-edge-colorings of G with no rainbow K4 is at most rex(n,K4), where ex(n,K4) denotes the Turán number of K4. Moreover, G attains equality if and only if it is the Turán graph T3(n). The bound on the number of colors r≥ 12 is best possible. It improves upon a result of H. Lefmann, D.A. Nolibos, and the second author who showed the same result for r ≥ 5434 and it confirms a conjecture by Gupta, Pehova, Powierski and Staden.