Improvement on the decay of crossing numbers

Details Improvement on the decay of crossing numbers Improvement on the decay of crossing numbers

2012-01-26

arxiv.org/abs/1201.5421v1

Mathematics

Combinatorics

7 pages, 1 figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Improvement on the decay of crossing numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improvement on the decay of crossing numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improvement on the decay of crossing numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444935