Maximum number of colourings. II. 5-chromatic graphs
classification
🧮 math.CO
keywords
colouringsgraphtomescuacadaddingchromaticchromatiquesconjecture
read the original abstract
In 1971, Tomescu conjectured [Le nombre des graphes connexes $k$-chromatiques minimaux aux sommets \'etiquet\'es, 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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.