The triangle-free cubic graph conjecture for the Clebsch graph
The triangle-free cubic graph conjecture for the Clebsch graph
Let be a cubic graph, meaning every vertex has degree . Let denote the four-dimensional projective cube, also known as the Clebsch graph. A graph homomorphism is a vertex map preserving adjacency.
Triangle-free cubic graph conjecture. Every triangle-free cubic graph is homomorphic to .
A graph containing a triangle cannot map to the triangle-free Clebsch graph, so triangle-freeness is the natural obstruction highlighted in the paper. The paper proves the assertion for cubic graphs of sufficiently large girth, but leaves the full triangle-free case unresolved.
Sources & referencesView supporting material
Primary source
Matt DeVos and Robert Samal, “High-girth cubic graphs are homomorphic to the Clebsch graph”, arXiv:math/0602580 (2009).
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.