×

The crossing number of \(C_m \times C_n\) is as conjectured for \(n\geq m(m+1)\). (English) Zbl 1053.05032

Summary: It has been long conjectured that the crossing number of \(C_m \times C_n\) is \((m-2)n\), for all \(m, n\) such that \(n\geq m\geq 3\). In this paper, it is shown that if \(n\geq m(m+1) \) and \(m\geq 3\), then this conjecture holds. That is, the crossing number of \(C_m \times C_n\) is as conjectured for all but finitely many \(n\), for each \(m\). The proof is largely based on techniques from the theory of arrangements, introduced by J. Adamsson [Ph.D. Thesis, Carleton University, 2000] and further developed by J. Adamsson and R. B. Richter [J. Comb. Theory, Ser. B 90, 21–39 (2004; Zbl 1033.05026)].

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 1033.05026
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ph.D. Thesis, Carleton University, 2000.
[2] Adamsson, J Combin Theory Series B 90 pp 21– (2004)
[3] Anderson, Cong Numerantium 118 pp 97– (1996)
[4] Anderson, Cong Numerantium 125 pp 97– (1997)
[5] Beineke, J Graph Theory 4 pp 145– (1980)
[6] Dean, J Graph Theory 19 pp 125– (1995)
[7] Harary, Nanta Math 6 pp 58– (1973)
[8] Hlin?ný, Lecture Notes in Comput Sci 2265 pp 102– (2000)
[9] Hlin?ný, J Combin Theory, Series B 88 pp 347– (2003)
[10] Juarez, J Combin Theory Series B 82 pp 161– (2001)
[11] Kle??, J Graph Theory 22 pp 239– (1996)
[12] Richter, Australasian J Combin 23 pp 135– (2001)
[13] Richter, Disc Comp Geom 13 pp 149– (1995)
[14] Ringeisen, J Combin Theory 24 pp 134– (1978)
[15] Shahrokhi, Discrete Comput Geom 19 pp 237– (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.