Galvin–Tetali conjecture on colorings of regular graphs

About 14 years old · traced to

Let cq(G)c_q(G) denote the number of proper qq-colorings of a graph GG. Let GG be an nn-vertex dd-regular graph, with q≥3q\ge 3, and let Kd,dK_{d,d} be the complete bipartite graph with parts of size dd. Galvin–Tetali conjecture. The number of proper qq-colorings satisfies

cq(G)≤cq(Kd,d)n/(2d).c_q(G) \le c_q(K_{d,d})^{n/(2d)}.

Galvin and Tetali proved the inequality for bipartite GG; the supplied text records proofs for the cases d=3d=3 and d=4d=4, 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

Never refreshed

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.