Back to Search
Start Over
Improvement on the decay of crossing numbers
- Source :
- Graphs and Combinatorics 29 (2013), Issue 3, 365-371
- Publication Year :
- 2012
-
Abstract
- We prove that the crossing number of a graph decays in a continuous fashion in the following sense. For any epsilon>0 there is a delta>0 such that for a sufficiently large n, every graph G with n vertices and m > n^{1+epsilon} edges, has a subgraph G' of at most (1-delta)m edges and crossing number at least (1-epsilon)cr(G). This generalizes the result of J. Fox and Cs. Toth.<br />Comment: 7 pages, 1 figure
- Subjects :
- Mathematics - Combinatorics
Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- arXiv
- Journal :
- Graphs and Combinatorics 29 (2013), Issue 3, 365-371
- Publication Type :
- Report
- Accession number :
- edsarx.1201.5421
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1007/s00373-012-1137-3