Maximum number of triangle-free edge colourings with five and six colours
Main Article Content
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$.
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$.
Article Details
How to Cite
Botler, F., Corsten, J., Dankovics, A., Frankl, N., Hàn, H., Jiménez, A., & Skokan, J.
(2019).
Maximum number of triangle-free edge colourings with five and six colours.
Acta Mathematica Universitatis Comenianae, 88(3), 495-499.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1181/686
Issue
Section
EUROCOMB 2019