-
Linear connectivity forces large complete bipartite minorsBöhme, Thomas ...Dokazano je, da za poljubna naravna števila ▫$a$▫, ▫$s$▫ in ▫$k$▫ obstaja tak ▫$N = N(s,k,a)$▫, da vsak ▫$\frac{31}{2} (a+1)▫$-povezan graf z vsaj ▫$N$▫ vozlišči bodisi vsebuje subdivizijo grafa ... ▫$K_{a,sk}$▫ ali pa minor, ki je izomorfen kopijam grafa ▫$K_{a,k}$▫. Pravzaprav za to zadostuje že povezanost ▫$3a+2$▫ in minimalna stopnja ▫$\frac{31}{2} (a+1) - 3$▫. V posebnem primeru, ko je▫$s=1$▫ in ▫$k=a$▫, sledi, da ima vsak dovolj velik ▫$\frac{31}{2} (a+1)$▫-povezan graf minor ▫$K_a$▫. To je prvi znani rezultat, v katerem linearna povezanost zagotavlja minor ▫$K_a$▫. Ta rezultat tudi posplošuje rezultate Böhmeja in Kostochke in dokazuje hipotezo Fon-Der-Flaassa. Kot dodatno netrivialno posledico dobimo še nov rezultat, ki je v tesni zvezi s Hadwigerjevo domnevo, in rezultat o disjunktnih minorjih ▫$K_{a,k}$▫, ki je podoben izreku Erdős-Pósa za disjunktne cikle v grafu.Source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 99, no. 3, 2009, str. 557-582)Type of material - article, component partPublish date - 2009Language - englishCOBISS.SI-ID - 15145049
Author
Böhme, Thomas |
Kawarabayashi, Ken-ichi |
Maharry, John |
Mohar, Bojan, 1956-
Topics
matematika |
teorija grafov |
minor grafa |
povezanost |
drevesna širina |
Hadwigerjeva hipoteza |
▫$k$▫-prepleteni graf |
grafi na ploskvah |
Eulerjeva formula |
lastnost Erdősa in Póse |
mathematics |
graph theory |
graph minor |
connectivity |
tree-width |
tree-decomposition |
path-decomposition |
complete graph minor |
unavoidable minor |
▫$k$▫-linked |
Hadwiger conjecture |
grid minor |
Vortex structure |
near embedding |
graphs on surfaces |
Euler's formula |
Erdős-Pósa property
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Böhme, Thomas | |
Kawarabayashi, Ken-ichi | |
Maharry, John | |
Mohar, Bojan, 1956- | 01931 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.