Other formats:
BibTeX
LaTeX
RIS
@article{1646039, author = {Bokal, Drago and Bracic, Mojca and Derňár, Marek and Hliněný, Petr}, article_location = {internet}, article_number = {1}, doi = {http://dx.doi.org/10.37236/7753}, keywords = {graph theory; crossing number; crossing-critical}, language = {eng}, issn = {1077-8926}, journal = {Electronic Journal of Combinatorics}, title = {On Degree Properties of Crossing-Critical Families of Graphs}, url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812}, volume = {26}, year = {2019} }
TY - JOUR ID - 1646039 AU - Bokal, Drago - Bracic, Mojca - Derňár, Marek - Hliněný, Petr PY - 2019 TI - On Degree Properties of Crossing-Critical Families of Graphs JF - Electronic Journal of Combinatorics VL - 26 IS - 1 SP - 1-28 EP - 1-28 PB - - SN - 10778926 KW - graph theory KW - crossing number KW - crossing-critical UR - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812 L2 - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812 N2 - 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) >= 3 and 3, 4 is an element of 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. ER -
BOKAL, Drago, Mojca BRACIC, Marek DERŇÁR and Petr HLINĚNÝ. On Degree Properties of Crossing-Critical Families of Graphs. \textit{Electronic Journal of Combinatorics}. internet: -, 2019, vol.~26, No~1, p.~1-28. ISSN~1077-8926. Available from: https://dx.doi.org/10.37236/7753.
|