Graph homomorphisms into the five-cycle (Q1105622)

From MaRDI portal
Revision as of 11:50, 13 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Graph homomorphisms into the five-cycle
scientific article

    Statements

    Graph homomorphisms into the five-cycle (English)
    0 references
    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

    Identifiers