General lower bounds for the minor crossing number of graphs

Drago Bokal (Author), Éva Czabarka (Author), László Székely (Author), Imrich Vrt'o (Author)

Abstract

There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. Inthis contribution, we present their adaptations to the minor crossing number. Using the adapted bounds, we improve on the known bounds on the minor crossing number of hypercubes. We also point out relations of the minor crossing number to string graphs.

Keywords

teorija grafov;prekrižno število;minor;hiper kocke;graph theory;minor crossing number;graph minor;string graphs;hypercubes;

Data

Language:	English
Year of publishing:	2008
Typology:	0 - Not set
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	14795353
ISSN:	1318-4865
Views:	0
Downloads:	0
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1-15
Volume:	ǂVol. ǂ46
Issue:	ǂšt. ǂ1054
Chronology:	2008
ID:	1473613