Abstract | ||
---|---|---|
. It was conjectured by Caccetta and Häggkvist in 1978 that every digraph G with n vertices and minimum outdegree at least r contains a directed cycle of length at most ⌈n/r⌉. By refining an argument of Chvátal and Szemerédi, we prove that such G contains a directed cycle of length at most n/r+73. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1007/s003730200048 | Graphs and Combinatorics |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Vertex (geometry),Conjecture,Digraph,Mathematics | Journal | 18 |
Issue | ISSN | Citations |
3 | 0911-0119 | 8 |
PageRank | References | Authors |
0.64 | 7 | 1 |