Graph homomorphisms into the five-cycle
type: Item
instance of: scholarly article
title: Graph homomorphisms into the five-cycle
zbMATH Open document ID: 0649.05056
DOI: 10.1016/0095-8956(88)90069-X
author: Paul A. Catlin
published in: Journal of Combinatorial Theory. Series B
publication date: 1988-01-01T00:00:00Z
review text: \textit{A. M. H. Gerards} [J. Graph Theory 12, 73-83 (1988)] proved that if a graph G with odd girth n does not admit a homomorphism into the cycle \(C_ n\) then G contains a special subdivision of \(K_ 4\) or \(K\) \(2_ 3\). The author presents a constructive characterization of those graphs which have no homomorphism into the cycle \(C_ 5\) and contain no subdivision of \(K_ 4\).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4059458
zbMATH Keywords: graph homomorphism
zbMATH Keywords: \(C_ 5\)-coloring of a graph
zbMATH Keywords: subgraph homeomorphic to \(K_ 4\)
reviewed by: Jozef Širáň
MaRDI profile type: Publication
cites work: Q3758851
cites work: Q3097395
cites work: Q5782525
cites work: Hajos' graph-coloring conjecture: Variations and counterexamples
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: Homomorphisms of graphs into odd cycles
cites work: Q5578801
cites work: A correction to: On the algebraic theory of graph colorings
full work available at URL: 0095-8956(88)90069-x
OpenAlex ID: W2068057399
description: scientific article; zbMATH DE number 4059458