Maximum number of colourings: 5-chromatic case (Q2323817)

Summary: \textit{I. Tomescu} [C. R. Acad. Sci., Paris, Sér. A 273, 1124--1126 (1971; Zbl 0223.05115)] conjectured 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\).