A note on short cycles in diagraphs

✍ Scribed by C.T Hoàng; B Reed

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 297 KB
• Volume: 66
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90122-1

✦ Synopsis

if G is a directed graph with n vertices and minimal outdegree k, then G contains a directed cycle of length at most In~k]. This conjecture is known to be true for k ~< 3. In this paper, we present a proof of the conjecture for the cases k = 4 and k = 5. We also present a new conjecture which implies that of Caccetta and Haggkvist. In 1977, Caccetta and Haggkvist [1] conjectured that if G is a directed graph with n vertices and if each vertex of G has outdegree at least k, then G contains a directed cycle of length at most In~k]. We shall refer to this conjecture as the C-H conjecture. Trivially, this conjecture is true for k = 1, and it has been proved for k =2 (Caccetta and Haggkvist [1]) and k = 3 (Hamildoune [3]). Chv~ital and Szemer6di [2] proved that the C-H conjecture holds if we replace the bound on the length of the cycle by In~k] + 2500. In this paper, we prove that the C-H conjecture holds for k ~< 5. Our main results are obtained by extending the arguments of Chv~ital and Szemer6di.

In order to prove the C-H conjecture for k ~< 5, we show first that if the conjecture fails for a small value of k, then it must fail on a reasonably small graph.