Abstract
At most how many (proper) q-colorings does a regular graph admit? Galvin and Tetali conjectured that among all n-vertex, d-regular graphs with 2d|n, none admits more q-colorings than the disjoint union of n/2d copies of the complete bipartite graph K d,d . In this note we give asymptotic evidence for this conjecture, showing that for each q ≥ 3 the number of proper q-colorings admitted by an n-vertex, d-regular graph is at most
where \({o(1)\rightarrow 0}\) as \({d \rightarrow \infty}\) ; these bounds agree up to the o(1) terms with the counts of q-colorings of n/2d copies of K d,d . Along the way we obtain an upper bound on the number of colorings of a regular graph in terms of its independence number. For example, we show that for all even q ≥ 4 and fixed ɛ > 0 there is \({\delta=\delta(\varepsilon,q)}\) such that the number of proper q-colorings admitted by an n-vertex, d-regular graph with no independent set of size \({n(1-\varepsilon)/2}\) is at most
with an analogous result for odd q.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon N.: Independent sets in regular graphs and sum-free subsets of finite groups. Isr. J. Math. 73, 247–256 (1991)
Bender E., Wilf H.: A theoretical analysis of backtracking in the graph coloring problem. J. Algorithms 6, 275–282 (1985)
Galvin D.: Maximizing H-colorings of regular graphs. J. Graph Theory 73, 66–84 (2013)
Galvin D.: An upper bound for the number of independent sets in regular graphs. Discrete Math. 309, 6635–6640 (2009)
Galvin, D., Tetali, P.: On weighted graph homomorphisms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. In: Graphs, Morphisms and Statistical Physics, vol. 63, pp. 97–104 (2004)
Jukna, S.: Extremal Combinatorics With Applications in Computer Science, 2nd edn. Springer, Berlin (2011)
Kahn J.: An entropy approach to the hard-core model on bipartite graphs. Comb. Probab. Comput. 10, 219–237 (2001)
Lazebnik F.: Some corollaries of a theorem of Whitney on the chromatic polynomial. Discrete Math. 87, 53–64 (1991)
Linial N.: Legal coloring of graphs. Combinatorica 6, 49–54 (1986)
Loh P.-S., Pikhurko O., Sudakov B.: Maximizing the Number of q-Colorings. Proc. Lond. Math. Soc. 101, 655–696 (2010)
Sapozhenko A.: The number of independent sets in graphs. Mosc. Univ. Math. Bull. 62, 116–118 (2007)
Wilf H.: Backtrack: an O(1) expected time algorithm for the graph coloring problem. Inf. Process. Lett. 18, 119–121 (1984)
Zhao Y.: The number of independent sets in a regular graph. Combin. Probab. Comput. 19, 315–320 (2010)
Zhao Y.: The bipartite swapping trick on graph homomorphisms. SIAM J. Discrete Math. 25, 660–680 (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported in part by the Simons Foundation and by NSA Grant H98230-13-1-0248.
Rights and permissions
About this article
Cite this article
Galvin, D. Counting Colorings of a Regular Graph. Graphs and Combinatorics 31, 629–638 (2015). https://doi.org/10.1007/s00373-013-1403-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-013-1403-z