2017/12/17 by Fox, Jacob, He, Xiaoyu, Manners, Freddie
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1712.06067
In 1971, Tomescu conjectured that every connected graph G on n vertices with chromatic number k≥4 has at most k!(k-1)n-k proper k-colorings. Recently, Knox and Mohar proved Tomescu's conjecture for k=4 and k=5. In this paper, we complete the proof of Tomescu's conjecture for all k≥ 4, and show that equality occurs if and only if G is a k-clique with trees attached to each vertex.