On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs
- 22 March 2016
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 84 (4) , 552-565
Abstract
The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number of G is the minimum number of crossings in a such drawing of G with edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound to urn:x-wiley:03649024:media:jgt22041:jgt22041-math-0004 and prove . We also show that for n large enough, and , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r‐partite graph. Richter and Thomassen proved in 1997 that the limit as of over the maximum number of crossings in a drawing of exists and is at most . We define and show that for a fixed r and the balanced complete r‐partite graph, is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.Keywords
All Related Versions
Funding Information
- National Science Foundation (DMS‐1266016)
This publication has 18 references indexed in Scilit:
- Applications of the Semi-Definite Method to the Turán Density Problem for 3-GraphsCombinatorics, Probability and Computing, 2012
- Non-Three-Colourable Common Graphs ExistCombinatorics, Probability and Computing, 2012
- A New Lower Bound Based on Gromov’s Method of Selecting Heavily Covered PointsDiscrete & Computational Geometry, 2012
- The crossing number ofDiscrete Mathematics, 2008
- The crossing number ofDiscrete Mathematics, 2008
- CSDP, A C library for semidefinite programmingOptimization Methods and Software, 1999
- Relations Between Crossing Numbers of Complete and Complete Bipartite GraphsThe American Mathematical Monthly, 1997
- The crossing number of K1,3,n and K2,3,nJournal of Graph Theory, 1986
- A note of welcomeJournal of Graph Theory, 1977
- On the Number of Crossings in a Complete GraphProceedings of the Edinburgh Mathematical Society, 1963