Premium
High‐girth cubic graphs are homomorphic to the Clebsch graph
Author(s) -
DeVos Matt,
Šámal Robert
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20580
Subject(s) - mathematics , combinatorics , cubic graph , foster graph , edge coloring , discrete mathematics , triangle free graph , symmetric graph , graph homomorphism , petersen graph , windmill graph , graph power , odd graph , graph , voltage graph , line graph , 1 planar 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šetřil's Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C 5 ). Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 241—259, 2011