2008
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 (203 Česká republika, garant) a Gelasio SALAZAR (484 Mexiko)
Vydání
Electronic Notes in Discrete Mathematics, Elsevier, 2008, 1571-0653
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Francie
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Kód RIV
RIV/00216224:14330/08:00024776
Organizační jednotka
Fakulta informatiky
UT WoS
000283762100003
Klíčová slova anglicky
crossing number; crossing-critical graph
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 24. 3. 2010 11:03, 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
| GA201/08/0308, projekt VaV |
|