bibkey: haggkvist1982oddcycles
authors: Roland Häggkvist
year: 1982
title: Odd Cycles of Specified Length in Non-Bipartite Graphs
doi: 10.1016/S0304-0208(08)73552-7
url: https://doi.org/10.1016/S0304-0208(08)73552-7
claim: Every finite triangle-free graph with minimum degree greater than three-eighths of its order admits a homomorphism to the five-cycle.
strata_touched:
  - D5/S3/Combinatorics/Graph/Walks/HaggkvistPentagonHomomorphism
license: citation-only
triage: anchor

Odd Cycles of Specified Length in Non-Bipartite Graphs

Verified locator

DOI: 10.1016/S0304-0208(08)73552-7

Source: https://doi.org/10.1016/S0304-0208(08)73552-7

Roland Häggkvist, in Graph Theory, Proceedings of the Conference on Graph Theory, North-Holland Mathematics Studies, volume 62, pages 89–99 (1982).

Attested claim

Every finite triangle-free graph with minimum degree greater than three-eighths of its order admits a homomorphism to the five-cycle. The strict inequality is 3 * |V(G)| < 8 * δ(G). Bipartite graphs are included, since a two-coloring maps them to an edge of the five-cycle.

The formal target is the five-cycle with vertices reindexed by multiplication by three in Fin 5. This reindexing preserves the homomorphism conclusion.

The chapter’s bibliographic metadata identifies the published source. Its full text has not been independently verified here; the attribution of the strict three-eighths theorem is the attestation carried by the cited result.