Projects per year
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 2edgecoloured 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 language  English 

Pages (fromto)  338351 
Number of pages  14 
Journal  Journal of Combinatorial Theory. Series B 
Volume  169 
Early online date  22 Jul 2024 
DOIs  
Publication status  Epub ahead of print  22 Jul 2024 
Fingerprint
Dive into the research topics of 'An oriented discrepancy version of Dirac's theorem'. Together they form a unique fingerprint.
Ramsey theory: an extremal perspective
Engineering & Physical Science Research Council
1/01/22 → 31/12/24
Project: Research Councils

Matchings and tilings in graphs
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils