A framework for the generalised Erdős-Rothschild problem and a resolution of the dichromatic triangle case

Abstract

The Erdős-Rothschild problem from 1974 asks for the maximum number of $s$-edge colourings in an $n$-vertex graph which avoid a monochromatic copy of $K_k$, given positive integers $n,s,k$. In this paper, we systematically study the generalisation of this problem to a given forbidden family of colourings of $K_k$. This problem typically exhibits a dichotomy whereby for some values of $s$, the extremal graph is the `trivial' one, namely the Turán graph on $k-1$ parts, with no copies of $K_k$; while for others, this graph is no longer extremal and determining the extremal graph becomes much harder. We generalise a framework developed for the monochromatic Erdős-Rothschild problem to the general setting and work in this framework to obtain our main results, which concern two specific forbidden families: triangles with exactly two colours, and improperly coloured cliques. We essentially solve these problems fully for all integers $s\ge 2$ and large $n$. In both cases we obtain an infinite family of structures which are extremal for some $s$, which are the first results of this kind. A consequence of our results is that for every non-monochromatic colour pattern, every extremal graph is complete partite. Our work extends work of Hoppen, Lefmann and Schmidt and of Benevides, Hoppen and Sampaio.

53 pages + 4 page appendix, 4 figures