An oriented discrepancy version of Dirac's theorem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910503001915392 |
|---|---|
| author | Freschi, Andrea Lo, Allan |
| author_facet | Freschi, Andrea Lo, Allan |
| contents | 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\geq3$ vertices with $δ(G)\geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_06950 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An oriented discrepancy version of Dirac's theorem Freschi, Andrea Lo, Allan Combinatorics 05C45 (Primary) 05C20, 05C07, 05C38 (Secondary) 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\geq3$ vertices with $δ(G)\geq 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. |
| title | An oriented discrepancy version of Dirac's theorem |
| topic | Combinatorics 05C45 (Primary) 05C20, 05C07, 05C38 (Secondary) |
| url | https://arxiv.org/abs/2211.06950 |