On the crossing number of K_m,n

MaRDI QIDQ1408549zbMATH OpenFDO

Authors Nagi H. Nahas

Publication date 24 September 2003

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/EJC/Volume_10/Abstracts/v10i1n8.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

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

Review text

Summary: The best lower bound known on the crossing number of the complete bipartite graph is \(\text{cr}(K_{m,n}) \geq (1/5)m(m-1)\lfloor n/2\rfloor\lfloor(n-1)/2\rfloor.\) We prove that \(\text{cr}(K_{m,n}) \geq (1/5)m(m-1)\lfloor n/2 \rfloor \lfloor (n-1)/2 \rfloor + 9.9 \times 10^{-6} m^2n^2\) for sufficiently large \(m\) and \(n\).

Recommendations

• Improved Bounds for the Crossing Numbers of Km,n and Kn
• The crossing number of \(K_{1,1,3,n}\).
• The crossing number of \(K_{1,m,n}\)
• Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming
• The crossing number of \(K_{2, 2, 2, n}\)

Cited in

(19)

• Rectilinear crossings in complete balanced \(d\)-partite \(d\)-uniform hypergraphs
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• Crossing numbers of nearly complete graphs and nearly complete bipartite graphs.
• Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming
• The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)
• scientific article; zbMATH DE number 5952049 (Why is no real title available?)
• The crossing number of the bipartite permutation graph
• The crossing number ofK1,3,n andK2,3,n
• Copositive optimization -- recent developments and applications
• On k-crossings and k-nestings of permutations
• scientific article; zbMATH DE number 2094521 (Why is no real title available?)
• <italic>K</italic><sub>1,1,<italic>m</italic></sub>□<italic>P</italic><sub><italic>n</italic></sub> 的交叉数
• A survey of graphs with known or bounded crossing numbers
• scientific article; zbMATH DE number 5238993 (Why is no real title available?)
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill
• Graph Drawing
• New lower bounds on crossing numbers of \(K_{m,n}\) from semidefinite programming
• On the crossing number of \(K_{ m } \square P_{n}\)

This page was built for publication: On the crossing number of \(K_{m,n}\)

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