# Girth vs. largest induced acyclic subgraph

I have a hopefully quick reference question. Given n vertex digraph G of out-degree T, and no 2 cycles (girth at least 3), what is the lower bound on number of vertices in the largest induced acyclic subgraph of G?

Without the girth constraint, the right answer is n/T (union of a bunch of T cliques). With the girth constraint, I am not even sure T matters, and hope maybe the answer is Omega(n). But anything much more than n/T would be useful.

This must have been studied, but Google is failing me ;). The best I could find is that directed chromatic number is roughly (log n)/log g, which means the largest "color" gives an acyclic induced subgraph of size at least n/log n. This is pretty good, except the bound only kicks in when girth is above log n or so (ugly formula). I feel something much better and cleaner should be known directly.

A directed graph with no $2$-cycles is oriented. If there is also an edge between every pair of vertices then it is a tournament. All acyclic tournaments are transitive, and a tournament on $n$ vertices is only guaranteed to have transitive subtournaments on $\log n$ vertices (a variant of Ramsey's theorem). So you can't do better than $\log n$ without bounding the maximum degree of your oriented graph.
• All I'm really saying is that random tournaments have girth at least $3$ and no acyclic subgraphs of size greater than $\log n$. So it's just an example showing that you do need some stronger assumption (on the girth, on $T$, or on something else) to do better than this. I posted it as an answer because you speculated that girth at least $3$ might be sufficient for $\Omega(n)$. Jun 25, 2017 at 10:15
A directed graph with out-degree at most $T$ has at most $Tn$ arcs. Therefore the underlying undirected graph is $2T$-degenerate, and hence its chromatic number is at most $2T+1$. Then the largest color class of the underlying graph would give you a lower bound $n/(2T+1)$.
• A strengthening of this argument, where you choose a large acyclic set greedily, gives $n/(T+1)$, which is the roughly $n/T$ mentioned in the question. Jun 25, 2017 at 10:18