The chromatic extremal conjecture for regular graphs

Let GG be an nn-vertex, dd-regular graph, let KqK_q be the complete graph on qq vertices, and let hom(G,Kq){\rm hom}(G,K_q) denote the number of graph homomorphisms from GG to KqK_q. Chromatic extremal conjecture. For every nn, dd and qq,

hom(G,Kq)hom(Kd,d,Kq)n/2d.{\rm hom}(G,K_q)\leq {\rm hom}(K_{d,d},K_q)^{n/2d}.

Equivalently, the number of proper qq-colorings satisfies cq(G)cq(Kd,d)n/2dc_q(G)\leq c_q(K_{d,d})^{n/2d}. The conjecture is open for all q3q\geq3; it is known when q=q(n,d)q=q(n,d) is sufficiently large, but the cited methods do not settle constant qq.

Sources & referencesView supporting material

Primary source

David Galvin, “Three tutorial lectures on entropy and counting”, arXiv:1406.7872 (2014).

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.