Bounding the Tripartite-Circle Crossing Number of Complete Tripartite Graphs

摘要

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 cr(K_(m,n))≤[n/2][(n-1)/2][m/2][(m-1)/2] and conjectured that equality holds. Harary and Hill [4] and independently Guy [3] conjectured that the crossing number of the complete graph K_n is cr(K_n)=1/4[n/2][(n-1)/2][(n-2)/2][(n-3)/2)]=:H(n).