PDF

Discussiones Mathematicae Graph Theory 27(3) (2007) 549-551
DOI: https://doi.org/10.7151/dmgt.1379

A PROOF OF THE CROSSING NUMBER OF K_3,n IN A SURFACE

Pak Tung Ho

Department of Mathematics, MATH 1044
Purdue University
West Lafayette, IN 47907-2067, USA
e-mail: pho@math.purdue.edu

Abstract

In this note we give a simple proof of a result of Richter and Siran by basic counting method, which says that the crossing number of K_3,n in a surface with Euler genus ε is

⎢ ⎣ n 2ε+2 ⎥ ⎦ ⎧ ⎨ ⎝ n−(ε+1) ⎛ ⎝ 1+ ⎢ ⎣ n 2ε+2 ⎥ ⎦ ⎞ ⎠ ⎫> ⎬ ⎭ .

Keywords: crossing number, bipartite graph, surface.

2000 Mathematics Subject Classification: 05C10.

References

[1]	R.K. Guy and T.A. Jenkyns, The toroidal crossing number of Km,n, J. Combin. Theory 6 (1969) 235-250, doi: 10.1016/S0021-9800(69)80084-0.
[2]	R.B. Richter and J. Siran, The crossing number of K3,n in a surface, J. Graph Theory 21 (1996) 51-54, doi: 10.1002/(SICI)1097-0118(199601)21:1<51::AID-JGT7>3.0.CO;2-L.
[3]	G. Ringel, Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg 28 (1965) 139-150, doi: 10.1007/BF02993245.
[4]	G. Ringel, Der vollständige paare Graph auf nichtorientierbaren Flächen, J. Reine Angew. Math. 220 (1965) 88-93, doi: 10.1515/crll.1965.220.88.

Received 11 September 2006
Accepted 21 March 2007