Maximum number of colourings. II. 5-chromatic graphs

Abstract

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

References in corpus (1)

• Extremal Restraints for Graph Colourings

Cited by in corpus (1)

• Tomescu's graph coloring conjecture for $\ell$-connected graphs