Homomorphisms of graphs into odd cycles

Abstract

Abstract We give a class of graphs G for which there exists a homomorphism (= adjacency preserving map) from V ( G ) to V ( C ), where C is the shortest odd cycle in G , thereby extending a result of Albertson, Catlin, and Gibbons. Our class of graphs is characterized by the following property: For each odd subdivision G ′ of G there exists a homomorphic map from V ( G ′) to V ( C ), where C ′ is the shortest odd cycle of G ′.