An oriented discrepancy version of Dirac's theorem

Andrea Freschi*, Allan Lo*

*Corresponding author for this work

Research output: Contribution to journalReview articlepeer-review

7 Downloads (Pure)

Abstract

The study of graph discrepancy problems, initiated by Erdős in the 1960s, has received renewed attention in recent years. In general, given a 2-edge-coloured graph G, one is interested in embedding a copy of a graph H in G with large discrepancy (i.e. the copy of H contains significantly more than half of its edges in one colour). Motivated by this line of research, Gishboliner, Krivelevich and Michaeli considered an oriented version of graph discrepancy for Hamilton cycles. In particular, they conjectured the following generalization of Dirac's theorem: if G is an oriented graph on n≥3 vertices with δ(G)≥n/2, then G contains a Hamilton cycle with at least δ(G) edges pointing forward. In this paper, we present a full resolution to this conjecture.
Original languageEnglish
Pages (from-to)338-351
Number of pages14
JournalJournal of Combinatorial Theory. Series B
Volume169
Early online date22 Jul 2024
DOIs
Publication statusE-pub ahead of print - 22 Jul 2024

Keywords

  • Hamilton cycles
  • Graph discrepancy
  • Oriented graphs

Fingerprint

Dive into the research topics of 'An oriented discrepancy version of Dirac's theorem'. Together they form a unique fingerprint.

Cite this