An oriented discrepancy version of Dirac's theorem

MaRDI QIDQ6417086zbMATH OpenFDO

Authors Andrea Freschi, Allan Lo

Publication date 13 November 2022

Mathematics Subject Classification ID

Vertex degrees (05C07) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: The study of graph discrepancy problems, initiated by ErdH{o}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 $ngeq3$ vertices with $delta(G)geqn/2$, then $G$ contains a Hamilton cycle with at least $delta(G)$ edges pointing forward. In this paper, we present a full resolution to this conjecture.

This page was built for publication: An oriented discrepancy version of Dirac's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6417086)