In 1971, Tomescu conjectured [Le nombre des graphes connexes $k$-chromatiques minimaux aux sommets étiquetés, C. R. Acad. Sci. Paris 273 (1971), 1124--1126] that every connected graph $G$ on $n$ vertices with $\chi(G) = k \geq 4$ has at most $k!(k-1)^{n-k}$$k$-colourings, where equality holds if and only if the graph is formed from $K_k$ by repeatedly adding leaves. In this note we prove (a strengthening of) the conjecture of Tomescu when $k=5$.
@article{10_37236_7879,
author = {Fiachra Knox and Bojan Mohar},
title = {Maximum number of colourings: 5-chromatic case},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {3},
doi = {10.37236/7879},
zbl = {1419.05077},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7879/}
}
TY - JOUR
AU - Fiachra Knox
AU - Bojan Mohar
TI - Maximum number of colourings: 5-chromatic case
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/7879/
DO - 10.37236/7879
ID - 10_37236_7879
ER -
%0 Journal Article
%A Fiachra Knox
%A Bojan Mohar
%T Maximum number of colourings: 5-chromatic case
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/7879/
%R 10.37236/7879
%F 10_37236_7879
Fiachra Knox; Bojan Mohar. Maximum number of colourings: 5-chromatic case. The electronic journal of combinatorics, Tome 26 (2019) no. 3. doi: 10.37236/7879
