Geodesic
On short cycles in triangle-free oriented graphs
Czechoslovak Mathematical Journal, Tome 68 (2018) no. 1, pp. 67-75 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.21136/CMJ.2017.0131-16
Classification : 05C20, 05C38
Keywords: oriented graph; cycle; minimum semidegree 
@article{10_21136_CMJ_2017_0131_16,
     author = {Ji, Yurong and Wu, Shufei and Song, Hui},
     title = {On short cycles in triangle-free oriented graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {67--75},
     year = {2018},
     volume = {68},
     number = {1},
     doi = {10.21136/CMJ.2017.0131-16},
     mrnumber = {3783585},
     zbl = {06861567},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0131-16/}
}
TY  - JOUR
AU  - Ji, Yurong
AU  - Wu, Shufei
AU  - Song, Hui
TI  - On short cycles in triangle-free oriented graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2018
SP  - 67
EP  - 75
VL  - 68
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0131-16/
DO  - 10.21136/CMJ.2017.0131-16
LA  - en
ID  - 10_21136_CMJ_2017_0131_16
ER  - 
%0 Journal Article
%A Ji, Yurong
%A Wu, Shufei
%A Song, Hui
%T On short cycles in triangle-free oriented graphs
%J Czechoslovak Mathematical Journal
%D 2018
%P 67-75
%V 68
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0131-16/
%R 10.21136/CMJ.2017.0131-16
%G en
%F 10_21136_CMJ_2017_0131_16
Ji, Yurong; Wu, Shufei; Song, Hui. On short cycles in triangle-free oriented graphs. Czechoslovak Mathematical Journal, Tome 68 (2018) no. 1, pp. 67-75. doi: 10.21136/CMJ.2017.0131-16

[1] Bang-Jensen, J., Gutin, G. Z.: Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics, Springer, London (2001). | DOI | MR | JFM

[2] Bondy, J. A.: Counting subgraphs a new approach to the Caccetta-Häggkvist conjecture. Discrete Math. 165-166 (1997), 71-80. | DOI | MR | JFM

[3] Caccetta, L., Häggkvist, R.: 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 | JFM

[4] Christofides, D., Keevash, P., Kühn, D., Osthus, D.: A semiexact degree condition for Hamilton cycles in digraphs. SIAM J. Discrete Math. 24 (2010), 709-756. | DOI | MR | JFM

[5] Hamburger, P., Haxell, P., Kostochka, A.: On directed triangles in digraphs. Electron. J. Comb. 14 (2007), Research Paper N19, 9 pages. | MR | JFM

[6] Hladký, J., Kráľ, D., Norin, S.: Counting flags in triangle-free digraphs. Extended abstracts of the 5th European Conf. on Combinatorics, Graph Theory and Applications Bordeaux, 2009, Elsevier, Amsterdam, Electronic Notes in Discrete Mathematics 34 J. Nešetřil et al. (2009), 621-625. | DOI | MR | JFM

[7] Keevash, P., Kühn, D., Osthus, D.: An exact minimum degree condition for Hamilton cycles in oriented graphs. J. Lond. Math. Soc., II. Ser. 79 (2009), 144-166. | DOI | MR | JFM

[8] Kelly, L., Kühn, D., Osthus, D.: A Dirac-type result on Hamilton cycles in oriented graphs. Comb. Probab. Comput. 17 (2008), 689-709. | DOI | MR | JFM

[9] Kelly, L., Kühn, D., Osthus, D.: Cycles of given length in oriented graphs. J. Comb. Theory, Ser. B 100 (2010), 251-264. | DOI | MR | JFM

[10] Kühn, D., Osthus, D.: A survey on Hamilton cycles in directed graphs. Eur. J. Comb. 33 (2012), 750-766. | DOI | MR | JFM

[11] Kühn, D., Osthus, D., Treglown, A.: Hamiltonian degree sequences in digraphs. J. Comb. Theory, Ser. B 100 (2010), 367-380. | DOI | MR | JFM

[12] Lichiardopol, N.: A new bound for a particular case of the Caccetta-Häggkvist conjecture. Discrete Math. 310 (2010), 3368-3372. | DOI | MR | JFM

[13] Razborov, A. A.: Flag algebras. J. Symb. Log. 72 (2007), 1239-1282. | DOI | MR | JFM

[14] Shen, J.: Directed triangles in digraphs. J. Comb. Theory, Ser. B 74 (1998), 405-407. | DOI | MR | JFM

[15] Sullivan, B. D.: A summary of results and problems related to the Caccetta-Häggkvist conjecture. Available at ArXiv:math/0605646v1 [math.CO] (2006).

Cité par Sources :