Other formats:
BibTeX
LaTeX
RIS
@article{818374,
author = {Hliněný, Petr},
article_location = {internet},
article_number = {1},
keywords = {crossing-critical; graph},
language = {eng},
issn = {1077-8926},
journal = {Electronic Journal of Combinatorics},
title = {New infinite families of almost-planar crossing-critical graphs},
url = {http://www.combinatorics.org/Volume_15/PDF/v15i1r46.pdf},
volume = {15},
year = {2008}
}
TY - JOUR
ID - 818374
AU - Hliněný, Petr
PY - 2008
TI - New infinite families of almost-planar crossing-critical graphs
JF - Electronic Journal of Combinatorics
VL - 15
IS - 1
SP - R102
EP - R102
PB - -
SN - 10778926
KW - crossing-critical
KW - graph
UR - http://www.combinatorics.org/Volume_15/PDF/v15i1r46.pdf
N2 - 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 their average degree can attain any rational value in the interval $\big[3+\frac15,6-\frac8{k+1}\big)$.
ER -
HLINĚNÝ, Petr. New infinite families of almost-planar crossing-critical graphs. \textit{Electronic Journal of Combinatorics}. internet: -, 2008, vol.~15, No~1, p.~R102, 12 pp. ISSN~1077-8926.
|
