The crossing number of K1,m,nK1,m,n

A longstanding problem of crossing number, Zarankiewicz’s conjecture, asserts that the crossing number of the complete bipartite graph Km,nKm,n is ⌊m2⌋⌊m−12⌋⌊n2⌋⌊n−12⌋, which is known only for m≤6m≤6. It is natural to generalize Zarankiewicz conjecture and ask: What is the crossing number for the complete multipartite graph? In this paper, we prove the following lower bounds for the crossing number of K1,m,nK1,m,n in terms of the crossing number of the complete bipartite graph: cr(K1,m,n)≥cr(Km+1,n+1)−⌊nm⌊m2⌋⌊m+12⌋⌋;cr(K1,2M,n)≥12(cr(K2M+1,n+2)+cr(K2M+1,n)−M(M+n−1)). As a corollary, we show that: 1.cr(K1,m,n)≥0.8594Z(m+1,n+1)−⌊nm⌊m2⌋⌊m+12⌋⌋;2.If Zarankiewicz’s conjecture is true for m=2M+1m=2M+1, then cr(K1,2M,n)=M2⌊n+12⌋⌊n2⌋−M⌊n2⌋;3.cr(K1,4,n)=4⌊n+12⌋⌊n2⌋−2⌊n2⌋.