Graph homomorphisms into the five-cycle

DOI10.1016/0095-8956(88)90069-XMaRDI QIDQ1105622zbMATH OpenOpenAlexFDO

Authors Paul A. Catlin

Publication date 1988

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(88)90069-x

zbMATH Keywords

\(C_ 5\)-coloring of a graphgraph homomorphismsubgraph homeomorphic to \(K_ 4\)

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph theory (05C99)

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\).

Recommendations

• Homomorphisms of graphs into odd cycles
• scientific article; zbMATH DE number 4008417
• scientific article; zbMATH DE number 1416059
• Homomorphisms of products of graphs into graphs without four cycles
• Graphs with odd girth at least seven and high minimum degree

Cites work

• A correction to: On the algebraic theory of graph colorings
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Graph theory with applications
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Homomorphisms of graphs into odd cycles
• scientific article; zbMATH DE number 4008417 (Why is no real title available?)
• scientific article; zbMATH DE number 3298599 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)

Cited in

(10)

• On colorings of graph powers
• On graphical quintuple systems
• Homomorphisms of products of graphs into graphs without four cycles
• Density of \(C_{-4}\)-critical signed graphs
• Smallest \(C_{2 \ell + 1}\)-critical graphs of odd-girth \(2 k + 1\)
• On the odd girth and the circular chromatic number of generalized Petersen graphs
• Homomorphisms of graphs into odd cycles
• scientific article; zbMATH DE number 4008417 (Why is no real title available?)
• Circular coloring of signed bipartite planar graphs
• Unique graph homomorphisms onto odd cycles. II

This page was built for publication: Graph homomorphisms into the five-cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105622)