On the decay of crossing numbers
Let \(\text{cr}(G)\) denote the crossing number of the graph \(G\). \textit{B. Richter} and \textit{C. Thomassen} [J. Comb. Theory, Ser. B 58, 217--224 (1993; Zbl 0733.05035)] conjectured that there is a constant \(c\) such that every graph \(G\) with crossing number \(k\) has an edge \(e\) such that \(\text{cr}(G-e)\geq k-c\sqrt{k}\), and showed that there is always an edge \(e\) such that \(\text{cr}(G-e)\geq 0.4k-O(1)\). The present paper shows that for every fixed \(\varepsilon>0\) there is a constant \(n_0\) depending on \(\varepsilon\) such that every graph graph \(G\) of order \(n>n_0\) and size \(m>n^{1+\varepsilon}\) has a subgraph \(G'\) with at most \((1-\varepsilon/24)m \) edges, such that \(\text{cr}(G') > ({1\over 28}-o(1))\text{cr}(G)\). The proofs revisit the bisection width and embedding methods.
- On the Decay of Crossing Numbers
- Improvement on the Decay of Crossing Numbers
- Improvement on the decay of crossing numbers
- On the degenerate crossing number
- Degenerate crossing numbers
- scientific article; zbMATH DE number 1047749
- scientific article; zbMATH DE number 1054768
- scientific article; zbMATH DE number 5019924
- On the decay of crossing numbers of sparse graphs
- New bounds on crossing numbers
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A Separator Theorem for Planar Graphs
- Applications of the crossing number
- Compactness results in extremal graph theory
- Crossing-Free Subgraphs
- 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?)
- Improving the crossing lemma by finding more crossings in sparse graphs
- Minimal graphs with crossing number at least \(k\)
- New bounds on crossing numbers
- New lower bound techniques for VLSI
- On a crossing number result of Richter and Thomassen
- Improvement on the crossing number of crossing-critical graphs
- The crossing number of \(K_{5,n+1} \setminus e\)
- Improvement on the decay of crossing numbers
- On the decay of crossing numbers of sparse graphs
- On the Decay of Crossing Numbers
- Improvement on the Crossing Number of Crossing-Critical Graphs
- Improvement on the Decay of Crossing Numbers
- Nested cycles in large triangulations and crossing-critical graphs
- Minimal graphs with crossing number at least \(k\)
This page was built for publication: 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 Q2464150)
