Nové nekonečné třídy téměř planárních průsečíkově kritických grafů

Kód výsledku v IS VaVaI

RIV/00216224:14330/08:00025241 - isvavai.cz

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

New infinite families of almost-planar crossing-critical graphs

Popis výsledku v původním jazyce

We show that, for all choices of integers $k>2$ and $m$, there are simple $3$-connected $k$-crossing-critical graphs containing more than $m$ vertices of each even degree $leq2k-2$. This construction answers one half of a question raised by Bokal, while the other half asking analogously about vertices of odd degrees at least $7$ in crossing-critical graphs remains open. Furthermore, our newly constructed graphs have several other interesting properties; for instance, they are almost planar and theiraverage degree can attain any rational value in the interval $big[3+frac15,6-frac8{k+1}big)$.

Název v anglickém jazyce

New infinite families of almost-planar crossing-critical graphs

Popis výsledku anglicky

We show that, for all choices of integers $k>2$ and $m$, there are simple $3$-connected $k$-crossing-critical graphs containing more than $m$ vertices of each even degree $leq2k-2$. This construction answers one half of a question raised by Bokal, while the other half asking analogously about vertices of odd degrees at least $7$ in crossing-critical graphs remains open. Furthermore, our newly constructed graphs have several other interesting properties; for instance, they are almost planar and theiraverage degree can attain any rational value in the interval $big[3+frac15,6-frac8{k+1}big)$.

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2008

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ů

Název periodika

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

—

Svazek periodika

15

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

12

Strana od-do

—

Kód UT WoS článku

000258122700003

EID výsledku v databázi Scopus

—