Improvement on the decay of crossing numbers
Popis výsledku
Identifikátory výsledku
Kód výsledku v IS VaVaI
Výsledek na webu
http://link.springer.com/article/10.1007%2Fs00373-012-1137-3
DOI - Digital Object Identifier
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Improvement on the decay of crossing numbers
Popis výsledku v původním jazyce
We prove that the crossing number of a graph decays in a "continuous fashion" in the following sense. For any epsilon > 0 there is a delta > 0 such that for a sufficiently large n, every graph G with n vertices and m a parts per thousand yen n (1+epsilon) edges, has a subgraph G' of at most (1 - delta)m edges and crossing number at least (1 - epsilon)CR(G). This generalizes the result of J. Fox and Cs. Tóth.
Název v anglickém jazyce
Improvement on the decay of crossing numbers
Popis výsledku anglicky
We prove that the crossing number of a graph decays in a "continuous fashion" in the following sense. For any epsilon > 0 there is a delta > 0 such that for a sufficiently large n, every graph G with n vertices and m a parts per thousand yen n (1+epsilon) edges, has a subgraph G' of at most (1 - delta)m edges and crossing number at least (1 - epsilon)CR(G). This generalizes the result of J. Fox and Cs. Tóth.
Klasifikace
Druh
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
GEGIG/11/E023: Kreslení grafů a jejich geometrické reprezentace
Návaznosti
S - Specificky vyzkum na vysokych skolach
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Graphs and Combinatorics
ISSN
0911-0119
e-ISSN
—
Svazek periodika
29
Číslo periodika v rámci svazku
3
Stát vydavatele periodika
JP - Japonsko
Počet stran výsledku
7
Strana od-do
365-371
Kód UT WoS článku
000318875700006
EID výsledku v databázi Scopus
—
Základní informace
Druh výsledku
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP
BA - Obecná matematika
Rok uplatnění
2013