Back to Search Start Over

Improvement on the decay of crossing numbers

Authors :
Černý, Jakub
Kynčl, Jan
Tóth, Géza
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

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