Campus Units

Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

4-2017

Journal or Book Title

Journal of Graph Theory

Volume

84

Issue

4

First Page

552

Last Page

565

DOI

10.1002/jgt.22041

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) over bar (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) over bar (K-n1,K- n2)
A(n1, n2, n3) :=

[GRAPHICS]

(left perpendicular n(j)/2 right perpendicular left perpendicular n(j)-1/2 right perpendicular left perpendicular n(k)/2 right perpendicular left perpendicular n(k)-1/2 right perpendicular + left perpendicular n(i)/2 right perpendicular left perpendicular n(i)-1/2 right perpendicular left perpendicular n(j)n(k)/2 right perpendicular),

and prove (cr) over bar (K-n1,K- n2,K- n3) infinity of cr(K-n,K- n) over the maximum number of crossings in a drawing of K-n,K- n exists and is at most 1/4. We define zeta(r) := 3(r(2) - r)/8(r(2) + r-3) and show that for a fixed r and the balanced complete r- partite graph, zeta(r) is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.

Comments

This is the peer-reviewed version of the following article: Gethner, Ellen, Leslie Hogben, Bernard Lidický, Florian Pfender, Amanda Ruiz, and Michael Young. "On crossing numbers of complete tripartite and balanced complete multipartite graphs." Journal of Graph Theory 84, no. 4 (2017): 552-565, which has been published in final form at DOI: 10.1002/jgt.22041. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving.

Copyright Owner

Wiley Periodicals, Inc.

Language

en

File Format

application/pdf

Published Version

Share

COinS