High Girth Cubic Graphs Map to the Clebsch

Hopkins and Staton [8] and Bondy and Locke [2] proved that every (sub)cubic graph of girth at least 4 has an edge-cut containing at least 4 5 of the edges. The existence of such an edge-cut follows immediatelyfrom the existence of a 5-edge-coloring as described above, so our theorem may be viewed as a kind of 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^set^ril's Pentagon Problem: Every cubic graph of sufficiently high girth maps to C5. 1 Introduction Throughout the paper all graphs are assumed to be finite, undirected andsimple. For any positive intege