Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition

Jiangdong Ai; Qiwen Guo; Gregory Gutin; Yongxin Lan; Qi Shao; Anders Yeo; Yacong Zhou; Jiangdong Ai; Qiwen Guo; Gregory Gutin; Yongxin Lan; Qi Shao; Anders Yeo; Yacong Zhou

doi:10.3934/math.2026972

AIMS Mathematics

2026, Volume 11, Issue 8: 24106-24119. doi: 10.3934/math.2026972

Previous Article Next Article

Research article Special Issues

Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition

1.
School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China
2.
Department of Computer Science, Royal Holloway, University of London, Surrey TW20 0EX, United Kingdom
3.
School of Science, Hebei University of Technology, Tianjin 300401, China
4.
Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China
5.
Department of Mathematics and Computer Science, University of Southern Denmark, Odense 5230, Denmark
6.
Department of Mathematics, University of Johannesburg, Johannesburg 2006, South Africa
7.
Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China

Received: 29 April 2026 Revised: 10 July 2026 Accepted: 17 July 2026 Published: 06 August 2026
MSC : 05C20, 05C45

Erdős (1963) initiated extensive graph discrepancy research on 2-edge-colored graphs. Gishboliner, Krivelevich, and Michaeli (2023) launched similar research on oriented graphs. They conjectured the following extension of Dirac's theorem: If $ D $ is an oriented graph on $ n \ge 3 $ vertices with minimum degree $ \delta (D) \ge n/ 2 $, then $ D $ contains a Hamilton oriented cycle with at least $ \delta(D) $ arcs in the same direction. This conjecture was proved by Freschi and Lo (2024) who posed an open problem to extend their result to an Ore-type condition. We proposed two conjectures for such extensions and proved results which provided support to the conjectures.
- oriented graphs,
- oriented discrepancy,
- Hamilton oriented cycles,
- Ore-type condition
Citation: Jiangdong Ai, Qiwen Guo, Gregory Gutin, Yongxin Lan, Qi Shao, Anders Yeo, Yacong Zhou. Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition[J]. AIMS Mathematics, 2026, 11(8): 24106-24119. doi: 10.3934/math.2026972

Related Papers:

Abstract

Erdős (1963) initiated extensive graph discrepancy research on 2-edge-colored graphs. Gishboliner, Krivelevich, and Michaeli (2023) launched similar research on oriented graphs. They conjectured the following extension of Dirac's theorem: If $ D $ is an oriented graph on $ n \ge 3 $ vertices with minimum degree $ \delta (D) \ge n/ 2 $, then $ D $ contains a Hamilton oriented cycle with at least $ \delta(D) $ arcs in the same direction. This conjecture was proved by Freschi and Lo (2024) who posed an open problem to extend their result to an Ore-type condition. We proposed two conjectures for such extensions and proved results which provided support to the conjectures.

References

[1]	J. Matoušek, Geometric discrepancy, Berlin: Springer, 1999. https://doi.org/10.1007/978-3-642-03942-3
[2]	P. Erdős, Ramsey és Van der Waerden tételével Kapcsolatos Kombinatorikai Kérdésekről, Mat. Lapok, 14 (1963), 29–37.
[3]	J. Balogh, B. Csaba, Y. Jing, A. Pluhár, On the discrepancies of graphs, Electron. J. Comb., 27 (2020), P2.12. https://doi.org/10.37236/8425 doi: 10.37236/8425
[4]	J. Balogh, B. Csaba, A. Pluhár, A. Treglown, A discrepancy version of the Hajnal–Szemerédi theorem, Comb. Probab. Comput., 30 (2021), 444–459. https://doi.org/10.1017/S0963548320000516 doi: 10.1017/S0963548320000516
[5]	A. Freschi, J. Hyde, J. Lada, A. Treglown, A note on colour-bias Hamilton cycles in dense graphs, SIAM J. Discrete Math., 35 (2021), 970–975. https://doi.org/10.1137/20M1378983 doi: 10.1137/20M1378983
[6]	L. Gishboliner, M. Krivelevich, P. Michaeli, Oriented discrepancy of Hamilton cycles, J. Graph Theory, 103 (2023), 780–792. https://doi.org/10.1002/jgt.22947 doi: 10.1002/jgt.22947
[7]	A. Freschi, A. Lo, An oriented discrepancy version of Dirac's theorem, J. Combin. Theory Ser. B, 169 (2024), 338–351. https://doi.org/10.1016/j.jctb.2024.06.008 doi: 10.1016/j.jctb.2024.06.008
[8]	J. Bang-Jensen, G. Z. Gutin, Digraphs: Theory, algorithms and applications, 2 Eds., London: Springer, 2009. https://doi.org/10.1007/978-1-84800-998-1
[9]	J. Bang-Jensen, G. Gutin, Basic terminology, notation and results, In: Classes of directed graphs, Cham: Springer, 2018, 1–34. https://doi.org/10.1007/978-3-319-71840-8_1
[10]	J. A. Bondy, U. S. R. Murty, Graph theory, London: Springer, 2008.
[11]	G. A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc., s3-2 (1952), 69–81. https://doi.org/10.1112/plms/s3-2.1.69 doi: 10.1112/plms/s3-2.1.69
[12]	O. Ore, Note on Hamiltonian circuits, Am. Math. Mon., 67 (1960), 55. https://doi.org/10.2307/2308928 doi: 10.2307/2308928
[13]	L. Pósa, On the circuits of finite graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., 8 (1963), 355–361.
[14]	Y. F. Chang, Y. Y. Cheng, Z. L. Wang, S. Wei, J. Yan, An Ore-type theorem for oriented discrepancy of Hamilton cycles, arXiv: 2603.18915, 2026. https://doi.org/10.48550/arXiv.2603.18915
[15]	S. Gerke, Q. Guo, G. Gutin, Y. Hao, W. Veeranonchai, A. Yeo, Backward arcs in Hamilton oriented cycles and paths in directed graphs with independence number two, arXiv: 2603.22993, 2026. https://doi.org/10.48550/arXiv.2603.22993
[16]	Q. Guo, G. Gutin, Y. Lan, Q. Shao, A. Yeo, Y. Zhou, Forward arc maximization for Hamilton oriented cycles and paths in generalizations of tournaments, arXiv: 2602.10713, 2026. https://doi.org/10.48550/arXiv.2602.10713
[17]	A. London, Notes on discrepancy and anti-discrepancy in oriented graphs, Discr. Appl. Math., 380 (2026), 283–289. https://doi.org/10.1016/j.dam.2025.10.019 doi: 10.1016/j.dam.2025.10.019

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)