Tomescu's Graph Coloring Conjecture for 𝓁-Connected Graphs

Authors

John Engbers, Marquette UniversityFollow
Aysel Erey, Gebze Technical University
Jacob Fox, Stanford University
Xiaoyu He, Stanford University

Document Type

Article

Publication Date

6-2021

Publisher

Society for Industrial and Applied Mathematics

Source Publication

SIAM Journal on Discrete Mathematics

Source ISSN

0895-4801

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 ℓ-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 ℓ≥3, we prove an asymptotically tight upper bound P_G(k)≤k!(k-1)^n-l-k+1+O((k – 2)ⁿ ) 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 δ.

Comments

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.

Recommended Citation

Engbers, John; Erey, Aysel; Fox, Jacob; and He, Xiaoyu, "Tomescu's Graph Coloring Conjecture for 𝓁-Connected Graphs" (2021). Mathematical and Statistical Science Faculty Research and Publications. 82.
https://epublications.marquette.edu/math_fac/82