4
$\begingroup$

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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi Ben. My apologies if I misunderstood your answer. I am looking for the size of the largest acyclic induced subgraph when the girth is at least 3, and the out degree is at most T. The value n/log n would be a good answer, although I am hoping for something like n/constant ideally. I am not looking at sub-tournaments or chromatic number, although they could be conceivably related. Thanks. $\endgroup$
    – Zaumka
    Commented Jun 25, 2017 at 5:41
  • $\begingroup$ 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)$. $\endgroup$
    – Ben Barber
    Commented Jun 25, 2017 at 10:15
0
$\begingroup$

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)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ this does not use the property that girth exceeds 2 $\endgroup$
    – Fedor Petrov
    Commented Jun 25, 2017 at 10:13
  • $\begingroup$ 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. $\endgroup$
    – Ben Barber
    Commented Jun 25, 2017 at 10:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .