High Girth Cubic Graphs Map to the Clebsch Graph
Matt DeVos, Robert Šámal · arXiv (Cornell University) · 2006
We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5-colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1).