Two recursive inequalities for crossing numbers of graphs

Zhangdong OUYANG; Jing WANG; Yuanqiu HUANG

doi:10.1007/s11464-016-0618-8

PDF(119 KB)

Front. Math. China ›› 2017, Vol. 12 ›› Issue (3) : 703-709. DOI: 10.1007/s11464-016-0618-8

RESEARCH ARTICLE

Two recursive inequalities for crossing numbers of graphs

Author information +

History +

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 \ e$ are determined, respectively.

Keywords

Graph / drawing / crossing number / recursive inequality

Cite this article

EndNote

Ris (Procite)

Bibtex

Download citation ▾

Zhangdong OUYANG, Jing WANG, Yuanqiu HUANG. Two recursive inequalities for crossing numbers of graphs. Front. Math. China, 2017, 12(3): 703‒709 https://doi.org/10.1007/s11464-016-0618-8

References

Publishing order | Descend order by publishing year | Descend order by cited within

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

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

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

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

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

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

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