2006/02/27 by Matt DeVos, Robert Šámal, DeVos, Matt +2
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.math/0602580
17 pages
openalex publication_date 2006/02/27 · arxiv created 2009/10/23 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Hopkins and Staton and Bondy and Locke 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 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 Nesetril's Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C5).