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:18 | comment | added | Ben Barber | 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:13 | comment | added | Fedor Petrov | this does not use the property that girth exceeds 2 | |
| Jun 25, 2017 at 10:10 | history | answered | Victor | CC BY-SA 3.0 |