Crossing number additivity over edge cuts

Bokal, Drago; Chimani, Markus; Leanõs, Jesús

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Crossing number additivity over edge cuts
Avtorji:	ID Bokal, Drago (Avtor) ID Chimani, Markus (Avtor) ID Leanõs, Jesús (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.ejc.2013.02.002
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
Opis:	Consider a graph $G$ with a minimal edge cut $F$ and let $G_1$ , $G_2$ be the two (augmented) components of $G-F$ . A long-open question asks under which conditions the crossing number of $G$ is (greater than or) equal to the sum ofcthe crossing numbers of $G_1$ and $G_2$ - which would allow us to consider those graphs separately. It is known that crossing number is additive for $\|F\| in {0,1,2}$ and that there exist graphs violating this property with $\|F\| ge 4$ . In this paper, we show that crossing number is additive for $\|F\|=3$ , thus closing the final gap in the question. The techniques generalize to show that minor crossing number is additive over edge cuts of arbitrary size, as well as to provide bounds for crossing number additivity in arbitrary surfaces. We point out several applications to exact crossing number computation and crossing-critical graphs, as well as provide a very general lower bound for the minor crossing number of the Cartesian product of an arbitrary graph with a tree.
Ključne besede:	matematika, teorija grafov, prekrižno število, minor, mathematics, graph theory, crossing number, minor
Leto izida:	2013
Št. strani:	str. 1010-1018
Številčenje:	Vol. 34, iss. 6
PID:	20.500.12556/DKUM-52013
UDK:	519.17
COBISS.SI-ID:	16624473
ISSN pri članku:	0195-6698
NUK URN:	URN:SI:UM:DK:CCTIUJTW
Datum objave v DKUM:	10.07.2015
Število ogledov:	1385
Število prenosov:	98
Metapodatki:
Področja:	Ostalo
:	BOKAL, Drago, CHIMANI, Markus in LEANÕS, Jesús, 2013, Crossing number additivity over edge cuts. European journal of combinatorics [na spletu]. 2013. Vol. 34, no. 6, p. 1010–1018. [Dostopano 24 april 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.ejc.2013.02.002 Kopiraj citat