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

About 3 years old · traced to

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 q≥4q\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 q≥4q\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.

References

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.