THE CROSSING NUMBER OF

Pak Tung Ho (U.S.A.)

Received December 12, 2006

References:

[1] K. Asano, The crossing number of and J. Graph Theory 10 (1986), 1-8. [2] E. deKlerk, J. Maharry, D. Pasechnik, R. B. Richter and G. Salazar, Improved bounds for the crossing numbers of and SIAM J. Discrete Math. 20 (2006), 189-202. [3] M. R. Garey and D. S. Johnson, Crossing number is NP-complete, SIAM J. Alg. Disc. Meth. 1 (1983), 312-316. [4] H. Harborth, Über die Kreuzungszahl vollständiger, n-geteilter Graphen, Math. Nachr. 48 (1971), 179-188. [5] H. Harborth, Parity of numbers of crossings for complete n-partite graphs, Math. Slovaca 26 (1976), 77-95. [6] P. T. Ho, On the crossing number of some complete multipartite graphs, Graphs Combin., submitted. [7] P. T. Ho, The crossing number of Discrete Math., submitted. [8] D. J. Kleitman, The crossing number of J. Combin. Theory 9 (1970), 315-323. [9] L. A. Székely, A successful concept for measuring non-planarity of graphs: the crossing number, Discrete Math. 276(1-3) (2004), 331-352. [10] D. R. Woodall, Cyclic-order graphs and Zarankiewicz’s crossing number conjecture, J. Graph Theory 17 (1993), 657-671.

Keywords and phrases: crossing number, multipartite graph.