2011/07/12 by Alexander Razborov, Razborov, Alexander
Engineering · Mathematics · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1107.2247
openalex publication_date 2011/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Caccetta-Haggkvist conjecture made in 1978 asserts that every orgraph on n vertices without oriented cycles of length <= l must contain a vertex of outdegree at most (n-1)/l. It has a rather elaborate set of (conjectured) extremal configurations. In this paper we consider the case l=3 that received quite a significant attention in the literature. We identify three orgraphs on four vertices each that are missing as an induced subgraph in all known extremal examples and prove the Caccetta-Haggkvist conjecture for orgraphs missing as induced subgraphs any of these orgraphs, along with cycles of length 3. Using a standard trick, we can also lift the restriction of being induced, although this makes graphs in our list slightly more complicated.