← All problems

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

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
  1. 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.