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.
Thank you in advance! Yevgeniy