New infinite families of almost-planar crossing-critical graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F08%3A00025241" target="_blank" >RIV/00216224:14330/08:00025241 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
New infinite families of almost-planar crossing-critical graphs
Original language description
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)$.
Czech name
Nové nekonečné třídy téměř planárních průsečíkově kritických grafů
Czech description
Ukážeme konstrukci jednoduchých 3-souvislých k-průsečíkově kritických grafů, které obsahují libovolně mnoho vrcholů sudých stupňů <=2k-2 pro všechna k>2. Tato konstrukce zodpovídá jednu polovinu otázky Bokala a má několik dalších zajímavých aplikací.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)