Edge-colorings avoiding patterns in a triangle

Abstract

For positive integers $n$ and $r$, we consider $n$-vertex graphs with the maximum number of $r$-edge-colorings with no copy of a triangle where exactly two colors appear. We prove that, if $2\le r\le 26$ and $n$ is sufficiently large, the maximum is attained by the bipartite Turán graph $T_2(n)$ on $n$ vertices. This is best possible, as $T_2(n)$ is not extremal for $r\ge 27$ colors and $n\ge 3$.

18 pages, 1 figure