Geodesic
Maximum number of triangle-free edge colourings with five and six colours
Fábio Botler1 ; Jan Corsten2 ; Attila János Dankovics2 ; Nóra Frankl2 ; Hiệp Hàn3 ; Andrea Jiménez3 ; Jozef Skokan2 ; Fábio Botler ; Jan Corsten ; Attila János Dankovics ; Nóra Frankl ; Hiệp Hàn ; Andrea Jiménez ; Jozef Skokan
1Alberto Luiz Coimbra Institute, Rio de Janeiro, Brazil
2London School of Economics and Political Science, Houghton St, London, UK
3Universidad de Valparaíso, Valparaíso, Región de Valparaíso, Chile
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 495-499 
Fábio Botler; Jan Corsten; Attila János Dankovics; Nóra Frankl; Hiệp Hàn; Andrea Jiménez; Jozef Skokan; Fábio Botler; Jan Corsten; Attila János Dankovics; Nóra Frankl; Hiệp Hàn; Andrea Jiménez; Jozef Skokan. Maximum number of triangle-free edge colourings with five and six colours. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 495-499. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a21/
@article{AMUC_2019_88_3_a21,
     author = {F\'abio Botler and Jan Corsten and Attila J\'anos Dankovics and N\'ora Frankl and Hiệp H\`an and Andrea Jim\'enez and Jozef Skokan and F\'abio Botler and Jan Corsten and Attila J\'anos Dankovics and N\'ora Frankl and Hiệp H\`an and Andrea Jim\'enez and Jozef Skokan},
     title = { Maximum number of triangle-free edge colourings with five and six colours},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {495--499},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a21/}
}
TY  - JOUR
AU  - Fábio Botler
AU  - Jan Corsten
AU  - Attila János Dankovics
AU  - Nóra Frankl
AU  - Hiệp Hàn
AU  - Andrea Jiménez
AU  - Jozef Skokan
AU  - Fábio Botler
AU  - Jan Corsten
AU  - Attila János Dankovics
AU  - Nóra Frankl
AU  - Hiệp Hàn
AU  - Andrea Jiménez
AU  - Jozef Skokan
TI  - Maximum number of triangle-free edge colourings with five and six colours
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 495
EP  - 499
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a21/
ID  - AMUC_2019_88_3_a21
ER  - 
%0 Journal Article
%A Fábio Botler
%A Jan Corsten
%A Attila János Dankovics
%A Nóra Frankl
%A Hiệp Hàn
%A Andrea Jiménez
%A Jozef Skokan
%A Fábio Botler
%A Jan Corsten
%A Attila János Dankovics
%A Nóra Frankl
%A Hiệp Hàn
%A Andrea Jiménez
%A Jozef Skokan
%T Maximum number of triangle-free edge colourings with five and six colours
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 495-499
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a21/
%F AMUC_2019_88_3_a21

Voir la notice de l'article provenant de la source Comenius University

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$.