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

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

Povzetek

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)|$▫.

Ključne besede

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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2008
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
UDK:	519.17
COBISS:	14499417
ISSN:	1077-8926
Št. ogledov:	39
Št. prenosov:	4
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Minorsko prekrižno število grafov s prepovedanim minorjem
Sekundarni povzetek:	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)\|$▫.
Sekundarne ključne besede:	matematika;teorija grafov;graf;grafovski minor;prepovedan minor;prekrižno število;minorsko prekrižno število;
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	R4 (13 str.)
Letnik:	ǂVol. ǂ15
Zvezek:	ǂno. ǂ1
Čas izdaje:	2008
ID:	67157