Improvement on the decay of crossing numbers

DOI10.1007/S00373-012-1137-3zbMATH Open1267.05068arXiv1201.5421OpenAlexW2761924117MaRDI QIDQ2376099FDOQ2376099

Authors: Jakub Černý, Jan Kynčl, Géza Tóth 

Publication date: 26 June 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1201.5421

Recommendations

• Improvement on the Decay of Crossing Numbers
• On the Decay of Crossing Numbers
• On the decay of crossing numbers
• On the decay of crossing numbers of sparse graphs
• An improvement of the crossing number bound

zbMATH Keywords

crossing numberembedding method

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Improving the crossing lemma by finding more crossings in sparse graphs
• The Moore bound for irregular graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the decay of crossing numbers
• Improvement on the Decay of Crossing Numbers
• Minimal graphs with crossing number at least \(k\)
• Title not available (Why is that?)

Cited In (5)

• On the decay of crossing numbers
• On the Decay of Crossing Numbers
• On the decay of crossing numbers of sparse graphs
• Improved upper bounds on the crossing number
• Improvement on the Decay of Crossing Numbers

This page was built for publication: Improvement on the decay of crossing numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2376099)