Galvin–Tetali conjecture on colorings of regular graphs
Let denote the number of proper -colorings of a graph . Let be an -vertex -regular graph, with , and let be the complete bipartite graph with parts of size . Galvin–Tetali conjecture. The number of proper -colorings satisfies
Galvin and Tetali proved the inequality for bipartite ; the supplied text records proofs for the cases and , while the conjecture remains open in general.
References
Primary source
Ashwin Sah, Mehtaab Sawhney, David Stoner and Yufei Zhao, “The number of independent sets in an irregular graph”, arXiv:1805.04021 (2019).
Additional references
4 papers in this index state this conjecture (2012–2018). The statement above is taken from the most recent of them; the others are arXiv:1610.08496, arXiv:1610.09210, arXiv:1205.2718.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.