Improvement on the decay of crossing numbers

Popis výsledku

—

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.

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

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ů

Druh výsledku

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

J_x

CEP

BA - Obecná matematika

Rok uplatnění

2013