Name
Abstract | ||
|---|---|---|
It is proved that for every constant ϵ > 0 and every graph G on n vertices which contains no odd cycles of length smaller than ϵn , G can be made bipartite by removing (15/ϵ)ln(10/ϵ)) vertices. This result is best possible except for a constant factor. Moreover, it is shown that one candestroy all odd cycles in such a graph G also by omitting not more than (200/ ϵ 2 )(ln(10/ ϵ )) 2 edges. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/0012-365X(95)00321-M | Discrete Mathematics |
Keywords | Field | DocType |
short odd cycle | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Bipartite graph,Mathematics | Journal |
Volume | Issue | ISSN |
163 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
5 | 0.80 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ervin Györi | 1 | 88 | 21.62 |
| Alexandr V. Kostochka | 2 | 682 | 89.87 |
| Tomasz Łuczak | 3 | 225 | 40.26 |