Perkins–Perarnau's coloring extremal conjecture for triangle-free and square-free cubic graphs
Let be a finite graph, let be the complete graph on vertices, and let denote the number of graph homomorphisms from to . Perkins–Perarnau's coloring extremal conjecture. (a) Provided that , among -regular triangle-free graphs , the quantity
is minimized when is the Petersen graph. (b) Among -regular graphs without cycles of length , the quantity
is maximized when is the Heawood graph. These assertions propose the extremal cubic graphs for normalized proper -coloring counts under the stated girth restrictions. The first assertion requires because the source gives a counterexample at ; 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
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.