TOMESCU'S GRAPH COLORING CONJECTURE FOR l-CONNECTED GRAPHS

Abstract

Let P-G(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 P-G(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 l-connected. For 2-connected graphs G, we prove a tight bound P-G(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 l >= 3, we prove an asymptotically tight upper bound P-G(k) <= k!(k-1)(n-l-k+1) + O((k-2)(n)) and provide a matching lower bound construction. For the ranges k >= l or l >= (k-2)(k-1) + 1 we further find the unique graph maximizing P-G(k). We also consider generalizing l-connected graphs to connected graphs with minimum degree delta.