Graph homomorphisms into the five-cycle (Q1105622)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4059458
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Graph homomorphisms into the five-cycle |
scientific article; zbMATH DE number 4059458 |
Statements
Graph homomorphisms into the five-cycle (English)
0 references
1988
0 references
\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\).
0 references
graph homomorphism
0 references
\(C_ 5\)-coloring of a graph
0 references
subgraph homeomorphic to \(K_ 4\)
0 references
0.8651156425476074
0 references
0.7845417261123657
0 references
0.7768443822860718
0 references
