## 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)^{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 Ξ΄*.*

## 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

## 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.