Bounding the Tripartite-Circle Crossing Number of Complete Tripartite Graphs

Bounding the Tripartite-Circle Crossing Number of Complete Tripartite Graphs 1 Introduction The crossing number of a graph G, denoted by cr(G), is the minimum number of edge-crossings over all drawings of G on the plane. To date, even the crossing numbers of complete and complete bipartite graphs are open. For the crossing number of the complete bipartite graph Zarankiewicz [6] showed that "! "! " ! "! n−1 m m−1 n , cr(Km,n ) ≤ 2 2 2 2 and conjectured that equality holds. Harary and Hill [4] and independently Guy [3] conjectured that the crossing number of the complete graph Kn is ! "! "! "! " 1 n n−1 n−2 n−3 =: H(n). cr(Kn ) = 4 2 2 2 2 The construction of Harary and Hill is a so-called cylindrical drawing, in which the vertices lie on the circles of a cylinder, and edges of the graph cannot cross the circles. Towards the Zarankiewicz Conjecture, these drawings can be restricted to bipartite cylindrical drawings, in which each set of the vertex partition lies on its own circle. A k-circle drawing of a graph G is a drawing of G in the plane where the vertices are placed on k disjoint circles and the edges do not cross the circles. The k-circle crossing number of a graph G is the minimum number of crossings in a k-circle drawing of G. For the special case when G is a k-partite graph, we can further require that each of the k vertex classes is placed on one of the k circles. The corresponding crossing number is called the k-partitecircle crossing number and is denoted by cr# k (G). Richter and Thomassen [5] #n $ showed that cr# 2 (Kn,n ) = n 3 . Ábrego, Fernández-Merchant, and Sparks [1] generalized this result for m ≤ n to % &% & + () n * ) n *+ () n * ) n * ' n m + cr# (K j − i j − i − n . ) = n,m 2 2 2 m m m m 0≤i