Maximum number of edge colorings avoiding rainbow copies of $K_4$
In this paper we show that for $r\geq 12$ and any sufficiently large $n$-vertex graph $G$ the number of $r$-edge-colorings of $G$ with no rainbow $K_4$ is at most $r^{ex(n,K_4)}$, where $ex(n,K_4)$ denotes the Tur\'{a}n number of $K_4$. Moreover, $G$ attains equality if and only if it is the Tur\'{a}n graph $T_3(n)$. The bound on the number of colors $r\geq 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 \geq 5434$ and it confirms a conjecture by Gupta, Pehova, Powierski and Staden.
Publication Details
- Journal
- ArXiv.org
- Published
- 2025-03-24
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00