Perkins–Perarnau's coloring extremal conjecture for triangle-free and square-free cubic graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.