Abstract | ||
---|---|---|
We prove that the crossing number of a graph decays in a “continuous fashion” in the following sense. For any ε> 0 there is a δ> 0 such that for n sufficiently large, every graph G with n vertices and m ≥ n
1 + ε
edges has a subgraph G′ of at most (1 − δ)m edges and crossing number at least
. This generalizes the result of J. Fox and Cs. Tóth.
|
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-540-77537-9_5 | Graphs and Combinatorics |
Keywords | DocType | Volume |
following sense,n vertex,graph decay,j. fox,graph g,subgraph g,continuous fashion,m edge,crossing number | Journal | 29 |
Issue | ISSN | ISBN |
3 | 1435-5914 | 3-540-77536-6 |
Citations | PageRank | References |
4 | 0.52 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jakub Cerný | 1 | 19 | 2.32 |
Jan Kyncl | 2 | 18 | 5.20 |
Géza Tóth | 3 | 581 | 55.60 |