Two recursive inequalities for crossing numbers of graphs

Abstract

In this paper, two recursive inequalities for crossing numbers of graphs are given by using basic counting method. As their applications, the crossing numbers of K_{1,3,n}and K_{4,n}\backslash e are determined, respectively.

Keywords

Graph / drawing / crossing number / recursive inequality

References

[1] AsanoK. The crossing number of K1,3,n and K2,3,n.J Graph Theory, 1980, 10: 1–8

[2] BondyJ A, MurtyU S R. Graph Theory with Applications. London: Macmillan Press Ltd, 1976

[3] GareyM R, JohnsonD S. Crossing number is NP-complete. SIAM J Algebraic Discrete Methods, 1983, 4: 312–316

[4] GroheM. Computing crossing number in quadratic time. In: Proceedings of the 33rd ACM Symposium on Theory of Computing STOC’01. 2001, 231–236

[5] HliněnýP. Crossing number is hard for cubic graphs. J Combin Theory Ser B, 2006, 96: 455–471

[6] KleitmanD J. The crossing number of K5,n.J Combin Theory, 1970, 9: 315–323

[7] SzékelyL A. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math, 2004, 276: 331–352

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg