On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament

Andrzej Grzesik¹

¹Faculty of Mathematics and Computer Science, Jagiellonian University, ul. St. Łojasiewicza 6, 30-348 Kraków, Poland

The electronic journal of combinatorics, Tome 24 (2017) no. 2

Résumé

The Caccetta-Häggkvist Conjecture asserts that every oriented graph on $n$ vertices without directed cycles of length less than or equal to $l$ has minimum outdegree at most $(n-1)/l$. In this paper we state a conjecture for graphs missing a transitive tournament on $2^k+1$ vertices, with a weaker assumption on minimum outdegree. We prove that the Caccetta-Häggkvist Conjecture follows from the presented conjecture and show matching constructions for all $k$ and $l$. The main advantage of considering this generalized conjecture is that it reduces the set of the extremal graphs and allows using an induction.We also prove the triangle case of the conjecture for $k=1$ and $2$ by using the Razborov's flag algebras. In particular, it proves the most interesting and studied case of the Caccetta-Häggkvist Conjecture in the class of graphs without the transitive tournament on 5 vertices. It is also shown that the extremal graph for the case $k=2$ has to be a blow-up of a directed cycle on 4 vertices having in each blob an extremal graph for the case $k=1$ (complete regular bipartite graph), which confirms the conjectured structure of the extremal examples.

Détail

DOI : 10.37236/5954

Classification : 05C20, 05C35, 05C07
Mots-clés : directed graph, transitive tournament, directed triangle, minimum outdegree