Geodesic
New infinite families of almost-planar crossing-critical graphs
The electronic journal of combinatorics, Tome 15 (2008)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
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+{1\over5},6-{8\over k+1}\big)$.
DOI : 10.37236/826
Classification : 05C10, 05C62
Mots-clés : crossing critical graphs, almost planar graphs, average degree 
Petr Hliněný. New infinite families of almost-planar crossing-critical graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/826
@article{10_37236_826,
     author = {Petr Hlin\v{e}n\'y},
     title = {New infinite families of almost-planar crossing-critical graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/826},
     zbl = {1165.05322},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/826/}
}
TY  - JOUR
AU  - Petr Hliněný
TI  - New infinite families of almost-planar crossing-critical graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/826/
DO  - 10.37236/826
ID  - 10_37236_826
ER  - 
%0 Journal Article
%A Petr Hliněný
%T New infinite families of almost-planar crossing-critical graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/826/
%R 10.37236/826
%F 10_37236_826

Cité par Sources :