Document Type


Publication Date



Society for Industrial and Applied Mathematics

Source Publication

SIAM Journal on Discrete Mathematics

Source ISSN



Let PG(k) be the number of proper k-colorings of a finite simple graph G. Tomescu's conjecture, which was recently solved by Fox, He, and Manners, states that PG(k)k!(k-1)(n – k) for all connected graphs G on n vertices with chromatic number kβ‰₯4. In this paper, we study the same problem with the additional constraint that G is β„“-connected. For 2-connected graphs G, we prove a tight bound PG(k)≀(k – 1)!((k – 1)(n – k+1) + ( - 1)n – k) and show that equality is only achieved if G is a k-clique with an ear attached. For β„“β‰₯3, we prove an asymptotically tight upper bound PG(k)≀k!(k-1)n-l-k+1+O((k – 2)n ) and provide a matching lower bound construction. For the ranges kβ‰₯β„“ or β„“ β‰₯ (k-2)(k-1)+ 1 we further find the unique graph maximizing . We also consider generalizing β„“-connected graphs to connected graphs with minimum degree Ξ΄.


Published version. SIAM Journal on Discrete Mathematics, Vol. 35, No. 2 (June 2021): 1478-1502. DOI. Β© 2021 Society for Industrial and Applied Mathematics. Used with permission.

engbers_14925acc.docx (241 kB)
ADA Accessible Version