The triangle-free cubic graph conjecture for the Clebsch graph

Let GG be a cubic graph, meaning every vertex has degree 33. Let PQ4PQ_4 denote the four-dimensional projective cube, also known as the Clebsch graph. A graph homomorphism GPQ4G\to PQ_4 is a vertex map preserving adjacency.

Triangle-free cubic graph conjecture. Every triangle-free cubic graph is homomorphic to PQ4PQ_4.

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

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.