On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs. Issue 4 (22nd March 2016)

• Record Type: Journal Article
• Authors: Gethner, Ellen; Hogben, Leslie; Lidický, Bernard; Pfender, Florian; Ruiz, Amanda; Young, Michael
• Is Part Of: Journal of graph theory. Volume 84:Issue 4(2017)
• Page Start: 552
• Page End: 565
• Publication Date: 2016-03-22
• Subjects: crossing number -- rectilinear crossing number -- complete tripartite graph -- complete multipartite graph -- balanced -- flag algebra -- 05C10 -- 05C62 -- 68R10; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22041
• Languages: English
• ISSNs: 0364-9024

Abstract

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 cr ¯ ( G ) 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 cr ¯ ( K n 1, n 2 ) ≤ Z ( n 1, n 2 ) : = ⌊ n 1 2 ⌋ ⌊ n 1 − 1 2 ⌋ ⌊ n 2 2 ⌋ ⌊ n 2 − 1 2 ⌋ . We generalize the upper bound Z ( n 1, n 2 ) to A ( n 1, n 2, n 3 ) : = ∑ i = 1, 2, 3 { j, k } = { 1, 2, 3 } ∖ { i } n j 2 n j − 1 2 n k 2 n k − 1 2 + n i 2 n i − 1 2 n j n k 2, and prove cr ¯ ( K n 1, n 2, n 3 ) ≤ A ( n 1, n 2, n 3 ) . We also show that for n large enough, 0.973 A ( n, n, n ) ≤ cr ¯ ( K n, n, n ) and 0.666 A ( n, n, n ) ≤ cr ( K n, n, n ), 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 n → ∞ of cr ( K n, n ) over the maximum number of crossings in a drawing of K n, n exists and is at most 1 4 . We define ζ ( r ) : = 3 ( r 2 − r ) 8 ( r 2 + r − 3 ) and show that for a fixed r and the balanced complete r ‐partite graph, ζ ( r ) is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.