Maximum number of triangle-free edge colourings with five and six colours

Abstract

Let $k\ge 3$ and $r\ge 2$ be natural numbers. For a graph $G$, let $F(G,k,r)$ denote the number of colourings of the edges of $G$ with colours $1,\dots,r$ such that, for every colour $c\in \{1,...,r\}$, the edges of colour $c$ contain no complete graph on $k$ vertices $K_k$. Let $F(n,k,r)$ denote the maximum of $F(G,k,r)$ over all graphs $G$ on $n$ vertices. The problem of determining $F(n,k,r)$ was first proposed by Erdős and Rothschild in 1974, and has so far been solved only for $r=2,3,$ and a small number of other cases.
In this paper we consider the question for the cases $k=3$ and $r=5$ or $r=6$. We almost exactly determine the value $F(n,3,6)$ and approximately determine the value $F(n,3,5)$ for large values of $n$. We also characterise all extremal graphs for $r=6$ and prove a stability result for $r=5$.