2017/08/05 by Fiachra Knox, Knox, Fiachra, Bojan Mohar +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1708.01781
It is proved that every connected graph G on n vertices with χ(G) ≥ 4 has at most k(k-1)n-3(k-2)(k-3) k-colourings for every k ≥ 4. Equality holds for some (and then for every) k if and only if the graph is formed from K4 by repeatedly adding leaves. This confirms (a strengthening of) the 4-chromatic case of a long-standing conjecture of Tomescu [Le nombre des graphes connexes k-chromatiques minimaux aux sommets etiquetes, C. R. Acad. Sci. Paris 273 (1971), 1124-1126]. Proof methods may be of independent interest. In particular, one of our auxiliary results about list-chromatic polynomials solves a recent conjecture of Brown, Erey, and Li.