Premium
Homomorphisms of graphs into odd cycles
Author(s) -
Gerards A. M. H.
Publication year - 1988
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.3190120108
Subject(s) - mathematics , combinatorics , homomorphism , subdivision , class (philosophy) , property (philosophy) , adjacency list , discrete mathematics , computer science , philosophy , archaeology , epistemology , artificial intelligence , history
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 ′.