High-girth cubic graphs are homomorphic to the Clebsch graph

摘要

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). Hopkins and Staton [J Graph Theory 6(2) (1982), 115-121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477-504] proved that every (sub)cubic graph of girth at least 4 has an edge-cut containing at least of the edges. The existence of such an edge-cut follows immediately from the existence of a 5-edge-coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above-described 5-edge-coloring; hence our theorem may also be viewed as a weak version of Ne?etr?il's Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C5).