The girth of digraphs and concatenating bipartite graphs

Abstract

We first disprove an old conjecture of Seymour which was a generalization of the famous Caccetta-Haggkvist conjecture, and then characterize when a bipartite digraph must contain a 2-cycle. Afterwards, we consider two functions Φ and Ψ, defi ned as follows. Let x,y ∈ (0; 1] and let A,B,C be disjoint nonempty subsets of a graph G, where every vertex in A has at least x|B| neighbors in B, and every vertex in B has at least y|C| neighbors in C. We denote by Φ(x,y) the maximum z such that, in all such graphs G, there is a vertex v ∈ C that is joined to at least z|A| vertices in A by two-edge paths. If in addition we require that every vertex in B has at least x|A| neighbors in A, and every vertex in C has at least y|B| neighbors in C, we denote by Ψ(x, y) the maximum z such that, in all such graphs G, there is a vertex v ∈ C that is joined to at least z|A| vertices in A by two-edge paths. In their recent paper [1], M. Chudnovsky, P. Hompe, A. Scott, P. Seymour, and S. Spirkl introduced these functions, proved some general results about them, and analyzed when they are greater than or equal to 1/2, 2/3, and 1/3. Here, we extend their results by analyzing when they are greater than or equal to 3/4, 2/5, and 3/5.