Improvement on the decay of crossing numbers

DOI10.1007/S00373-012-1137-3MaRDI QIDQ2376099zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1054768 (Why is no real title available?)
• scientific article; zbMATH DE number 1452728 (Why is no real title available?)
• scientific article; zbMATH DE number 2145249 (Why is no real title available?)
• Improvement on the Decay of Crossing Numbers
• Improving the crossing lemma by finding more crossings in sparse graphs
• Minimal graphs with crossing number at least \(k\)
• On the decay of crossing numbers
• The Moore bound for irregular graphs

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)