Nešetřil's Pentagon Conjecture for high-girth cubic graphs

About 20 years old · traced to

Let GG be a cubic graph and let its girth be the length of its shortest cycle. A graph homomorphism G→C5G\to C_5 is a vertex map preserving adjacency.

Nešetřil's Pentagon Conjecture. If GG is a cubic graph of sufficiently high girth, then GG is homomorphic to C5C_5.

Equivalently, sufficiently high-girth cubic graphs should have circular chromatic number at most 5/25/2. The statement is known with C3C_3 in place of C5C_5, while replacing C5C_5 by C7C_7 is false; the Pentagon Conjecture itself remains open.

References

Primary source

Matt DeVos and Robert Samal, “High-girth cubic graphs are homomorphic to the Clebsch graph”, arXiv:math/0602580 (2009).

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.