ǂThe ǂminor crossing number of graphs with an excluded minor

Drago Bokal (Author), Gašper Fijavž (Author), David Richard Wood (Author)

Abstract

Minorsko prekrižno število grafa ▫$G$▫ je najmanjše prekrižno število kakega grafa, ki vsebuje ▫$G$▫ kot minor. V prispevku pokažemo, da za vsak graf ▫$H$▫ obstaja konstanta ▫$c>0$▫, tako da ima vsak graf brez ▫$H$▫-minorja minorsko prekrižno število enako največ ▫$c|V(G)|$▫.

Keywords

matematika;teorija grafov;graf;grafovski minor;prepovedan minor;prekrižno število;minorsko prekrižno število;mathematics;graph theory;graph minor;excluded minor;crossing number;minor crossing number;

Data

Language:	English
Year of publishing:	2008
Typology:	1.01 - Original Scientific Article
Organization:	UL FRI - Faculty of Computer and Information Science
UDC:	519.17
COBISS:	14499417
ISSN:	1077-8926
Views:	39
Downloads:	4
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Minorsko prekrižno število grafov s prepovedanim minorjem
Secondary abstract:	The minor crossing number of a graph ▫$G$▫ is the minimum crossing number of a graph that contains ▫$G$▫ as a minor. It is proved that for every graph ▫$H$▫ there is a constant ▫$c$▫, such that every graph ▫$G$▫ with no ▫$H$▫-minor has minor crossing number at most ▫$c\|V(G)\|$▫.
Secondary keywords:	matematika;teorija grafov;graf;grafovski minor;prepovedan minor;prekrižno število;minorsko prekrižno število;
Type (COBISS):	Not categorized
Pages:	R4 (13 str.)
Volume:	ǂVol. ǂ15
Issue:	ǂno. ǂ1
Chronology:	2008
ID:	67157