Czechoslovak Mathematical Journal, Vol. 68, No. 1, pp. 67-75, 2018
On short cycles in triangle-free oriented graphs
Yurong Ji, Shufei Wu, Hui Song
Received March 18, 2016. First published December 5, 2017.
Abstract: An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $\lceil n / d\rceil$. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that $\alpha_0$ is the smallest real such that every $n$-vertex digraph with minimum outdegree at least $\alpha_0n$ contains a directed triangle. Let $\epsilon< {(3-2\alpha_0)}/{(4-2\alpha_0)}$ be a positive real. We show that if $D$ is an oriented graph without directed triangles and has minimum outdegree and minimum indegree at least $(1/{(4-2\alpha_0)}+\epsilon)|D|$, then each vertex of $D$ is contained in a directed cycle of length $l$ for each $4\le l< {(4-2\alpha_0)\epsilon|D|}/{(3-2\alpha_0)}+2$.
References: [1] J. Bang-Jensen, G. Z. Gutin: Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics, Springer, London (2001). DOI 10.1007/978-1-84800-998-1 | MR 1798170 | Zbl 0958.05002
[2] J. A. Bondy: Counting subgraphs a new approach to the Caccetta-Häggkvist conjecture. Discrete Math. 165-166 (1997), 71-80. DOI 10.1016/S0012-365X(96)00162-8 | MR 1439261 | Zbl 0872.05016
[3] L. Caccetta, R. Häggkvist: On minimal digraphs with given girth. Proc. 9th Southeast. Conf. on Combinatorics, Graph Theory, and Computing: Florida Atlantic University. Boca Raton, 1978 Congress. Numer. 21, Utilitas Math. Publishing, Winnipeg (1978), 181-187. MR 0527946 | Zbl 0406.05033
[4] D. Christofides, P. Keevash, D. Kühn, D. Osthus: A semiexact degree condition for Hamilton cycles in digraphs. SIAM J. Discrete Math. 24 (2010), 709-756. DOI 10.1137/090761756 | MR 2680211 | Zbl 1223.05162
[5] P. Hamburger, P. Haxell, A. Kostochka: On directed triangles in digraphs. Electron. J. Comb. 14 (2007), Research Paper N19, 9 pages. MR 2350447 | Zbl 1157.05311
[6] J. Hladký, D. Král', S. Norin: Counting flags in triangle-free digraphs. Extended abstracts of the 5th European Conf. on Combinatorics, Graph Theory and Applications (J. Nešetřil, et al.). Bordeaux, 2009, Elsevier, Amsterdam, Electronic Notes in Discrete Mathematics 34, (2009), 621-625. DOI 10.1016/j.endm.2009.07.105 | MR 2720903 | Zbl 1273.05107
[7] P. Keevash, D. Kühn, D. Osthus: An exact minimum degree condition for Hamilton cycles in oriented graphs. J. Lond. Math. Soc., II. Ser. 79 (2009), 144-166. DOI 10.1112/jlms/jdn065 | MR 2472138 | Zbl 1198.05081
[8] L. Kelly, D. Kühn, D. Osthus: A Dirac-type result on Hamilton cycles in oriented graphs. Comb. Probab. Comput. 17 (2008), 689-709. DOI 10.1017/S0963548308009218 | MR 2454564 | Zbl 1172.05038
[9] L. Kelly, D. Kühn, D. Osthus: Cycles of given length in oriented graphs. J. Comb. Theory, Ser. B 100 (2010), 251-264. DOI 10.1016/j.jctb.2009.08.002 | MR 2595670 | Zbl 1274.05257
[10] D. Kühn, D. Osthus: A survey on Hamilton cycles in directed graphs. Eur. J. Comb. 33 (2012), 750-766. DOI 10.1016/j.ejc.2011.09.030 | MR 2889513 | Zbl 1239.05114
[11] D. Kühn, D. Osthus, A. Treglown: Hamiltonian degree sequences in digraphs. J. Comb. Theory, Ser. B 100 (2010), 367-380. DOI 10.1016/j.jctb.2009.11.004 | MR 2644240 | Zbl 1209.05138
[12] N. Lichiardopol: A new bound for a particular case of the Caccetta-Häggkvist conjecture. Discrete Math. 310 (2010), 3368-3372. DOI 10.1016/j.disc.2010.07.026 | MR 2721097 | Zbl 1222.05087
[13] A. A. Razborov: Flag algebras. J. Symb. Log. 72 (2007), 1239-1282. DOI 10.2178/jsl/1203350785 | MR 2371204 | Zbl 1146.03013
[14] J. Shen: Directed triangles in digraphs. J. Comb. Theory, Ser. B 74 (1998), 405-407. DOI 10.1006/jctb.1998.1839 | MR 1654164 | Zbl 0904.05035
[15] B. D. Sullivan: A summary of results and problems related to the Caccetta-Häggkvist conjecture. Available at ArXiv:math/0605646v1 [math.CO] (2006).
Affiliations: Yurong Ji, School of Mathematics and Information Science, Henan Polytechnic University, Shiji Road, Gaoxin, Jiaozuo 454003, Henan, China, e-mail: jiyurong@hpu.edu.cn; Shufei Wu (corresponding author), School of Mathematics and Information Science, Henan Polytechnic University, Shiji Road, Gaoxin, Jiaozuo 454003, Henan, China; and Center for Discrete Mathematics, Fuzhou University, Qi Shan Campus of Fuzhou University, 2 Xue Yuan Road, University Town, Fuzhou 350003, Fujian, China, e-mail: shufeiwu@hotmail.com; Hui Song, Center for Discrete Mathematics, Fuzhou University, Qi Shan Campus of Fuzhou University, 2 Xue Yuan Road, University Town, Fuzhou 350003, Fujian, China, e-mail: songhuicc@hotmail.com
