Timeline for Girth vs. largest induced acyclic subgraph
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 25, 2017 at 10:15 | comment | added | Ben Barber | 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 5:41 | comment | added | Zaumka | 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. | |
| Jun 24, 2017 at 12:09 | history | answered | Ben Barber | CC BY-SA 3.0 |