A Summary of Problems and Results related to the Caccetta-Haggkvist Conjecture

Abstract

This paper is an attempt to survey the current state of our knowledge on the Caccetta-Haggkvist conjecture and related questions. In January 2006 there was a workshop hosted by the American Institute of Mathematics in Palo Alto, on the Caccetta-Haggkvist conjecture, and this paper partly originated there, as a summary of the open problems and partial results presented at the workshop. This summary includes results and open problems related to Caccetta-Haggkvist, Seymour's Second Neighborhood Conjecture, the k/2 Conjecture (for nonedges), and connections with algebraic number theory through Cayley graphs, along with a number of other related topics.

arXiv comment14 pages, 0 figures

Cited by in corpus (9)

• The inducibility of oriented stars
• Embedding cycles of given length in oriented graphs
• Growth of graph powers
• On the number of vertex-disjoint cycles in digraphs
• Dipaths of length at least double the minimum outdegree
• Short rainbow cycles in graphs and matroids
• Properly colored short cycles in edge-colored graphs
• Seymour's Second Neighborhood Conjecture for Subsets of Vertices
• Outdegree conditions forcing short cycles in digraphs