Answering an open question from 2007, we construct infinite $k$-crossing-critical families of graphs that contain vertices of any prescribed odd degree, for any sufficiently large $k$. To answer this question, we introduce several properties of infinite families of graphs and operations on the families allowing us to obtain new families preserving those properties. This conceptual setup allows us to answer general questions on behaviour of degrees in crossing-critical graphs: we show that, for any set of integers $D$ such that $\min(D)\geq 3$ and $3,4\in D$, and for any sufficiently large $k$, there exists a $k$-crossing-critical family such that the numbers in $D$ are precisely the vertex degrees that occur arbitrarily often in (large enough) graphs of this family. Furthermore, even if both $D$ and some average degree in the interval $(3,6)$ are prescribed, $k$-crossing-critical families exist for any sufficiently large $k$.
@article{10_37236_7753,
author = {Drago Bokal and Mojca Bra\v{c}i\v{c} and Marek Der\v{n}\'ar and Petr Hlin\v{e}n\'y},
title = {On degree properties of crossing-critical families of graphs},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {1},
doi = {10.37236/7753},
zbl = {1409.05066},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7753/}
}
TY - JOUR
AU - Drago Bokal
AU - Mojca Bračič
AU - Marek Derňár
AU - Petr Hliněný
TI - On degree properties of crossing-critical families of graphs
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7753/
DO - 10.37236/7753
ID - 10_37236_7753
ER -
%0 Journal Article
%A Drago Bokal
%A Mojca Bračič
%A Marek Derňár
%A Petr Hliněný
%T On degree properties of crossing-critical families of graphs
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7753/
%R 10.37236/7753
%F 10_37236_7753
Drago Bokal; Mojca Bračič; Marek Derňár; Petr Hliněný. On degree properties of crossing-critical families of graphs. The electronic journal of combinatorics, Tome 26 (2019) no. 1. doi: 10.37236/7753
