Perkins–Perarnau's coloring extremal conjecture for triangle-free and square-free cubic graphs

Let GG be a finite graph, let KqK_q be the complete graph on qq vertices, and let hom(G,Kq)\hom(G,K_q) denote the number of graph homomorphisms from GG to KqK_q. Perkins–Perarnau's coloring extremal conjecture. (a) Provided that q4q\geq 4, among 33-regular triangle-free graphs GG, the quantity

hom(G,Kq)1/V(G)\hom(G,K_q)^{1/|V(G)|}

is minimized when GG is the Petersen graph. (b) Among 33-regular graphs GG without cycles of length 44, the quantity

hom(G,Kq)1/V(G)\hom(G,K_q)^{1/|V(G)|}

is maximized when GG is the Heawood graph. These assertions propose the extremal cubic graphs for normalized proper qq-coloring counts under the stated girth restrictions. The first assertion requires q4q\geq 4 because the source gives a counterexample at q=3q=3; the status of the two assertions is otherwise left open in the source.

Sources & referencesView supporting material

Primary source

Stijn Cambie and Jorik Jooken, “Counterexamples to conjectures on the occupancy fraction of graphs”, arXiv:2311.05542 (2023).

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.