A proof of Tomescu's graph coloring conjecture

摘要

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. (C) 2018 Elsevier Inc. All rights reserved.