2010
Stars and Bonds in Crossing-Critical Graphs
HLINĚNÝ, Petr a Gelasio SALAZARZákladní údaje
Originální název
Stars and Bonds in Crossing-Critical Graphs
Název česky
Hvězdy a řezy v průsečíkově kritických grafech
Autoři
HLINĚNÝ, Petr ORCID a Gelasio SALAZAR
Vydání
Journal of Graph Theory, New York, John Wiley & Sons, 2010, 0364-9024
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 0.561
Označené pro přenos do RIV
Ano
Kód RIV
RIV/00216224:14330/10:00045366
Organizační jednotka
Fakulta informatiky
UT WoS
Klíčová slova anglicky
crossing number; crossing-critical graph
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 25. 11. 2011 13:42, prof. RNDr. Petr Hliněný, Ph.D.
V originále
The structure of all known infinite families of crossing--critical graphs has led to the conjecture that crossing--critical graphs have bounded bandwidth. If true, this would imply that crossing--critical graphs have bounded degree, that is, that they cannot contain subdivisions of $K_{1,n}$ for arbitrarily large $n$. In this paper we prove two results that revolve around this conjecture. On the positive side, we show that crossing--critical graphs cannot contain subdivisions of $K_{2,n}$ for arbitrarily large $n$. On the negative side, we show that there are graphs with arbitrarily large maximum degree that are $2$-crossing--critical in the projective plane.
Česky
Prezentujeme dva přístupy k dosud otevřené domněnce, že průsečíkově kritické grafy mají omezený maximální stupeň. Na pozitivní straně dokazujeme, že tyto grafy nemohou obsahovat subdivizi velkého K_2,n, ale na negativní straně ukazujeme neplatnost domněnky v projektivní rovině.
Návaznosti
| MSM0021622419, záměr |
|