Maximum number of colourings. II. 5-chromatic graphs

2017/10/18 by Knox, Fiachra, Mohar, Bojan
#05C15 #05C31 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1710.06535

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 χ(G) = k ≥ 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.

Related

• Maximum number of colourings. I. 4-chromatic graphs
• A proof of Tomescu's graph coloring conjecture
• Tomescu's graph coloring conjecture for ℓ-connected graphs
• Simultaneous edge-colourings
• Exponentially Many Correspondence Colourings of Planar and Locally Planar Graphs