关于完全3-部图K_(1,6,n)的交叉数

On the Crossing Number of the Complete Tripartite K_(1,6,n)

早在上世纪五十年代,Zarankiewicz猜想完全2-部图Km,n(m≤n)的交叉数为[m/2][m-1/2][n/2][n-1/2](对任意实数x,[x]表示不超过x的最大整数)．目前这一猜想的正确只证明了当m≤6时成立．本文主要证明了若Zarankiewicz猜想对m=7成立,则完全3-部图K1,6,n的交叉数为9[n/2][n-1/2]+6[n/2]．

Earily in the fifties of the 19th century, Zarankiewicz conjectured that the crossing number of the complete partite graph Km,n （m≤ n） is [m/2][m-1/2][n/2][n-1/2]（for any real number x, [x] denotes the maximum integer that is no more than x）. At present, the truth of this conjecture has been proved for the case m ≤ 6. In this papaer we prove that if Zarankiewicz＇s conjecture is true for the case m = 7, then the crossing number of the complete tripartite graph K1,6,n is 9[n/2][n-1/2]＋6[n/2].