Name
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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1137/19M1306646 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
graph coloring, connectivity, Tomescu's conjecture | Journal | 35 |
Issue | ISSN | Citations |
2 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Engbers | 1 | 21 | 6.79 |
| Aysel Erey | 2 | 19 | 4.99 |
| Jacob Fox | 3 | 123 | 22.33 |
| Xiaoyu He | 4 | 0 | 1.35 |