On Degree Properties of Crossing-Critical Families of Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00108270" target="_blank" >RIV/00216224:14330/19:00108270 - isvavai.cz</a>
Result on the web
<a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812" target="_blank" >https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.37236/7753" target="_blank" >10.37236/7753</a>
Alternative languages
Result language
angličtina
Original language name
On Degree Properties of Crossing-Critical Families of Graphs
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA17-00837S" target="_blank" >GA17-00837S: Structural properties, parameterized tractability and hardness in combinatorial problems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Electronic Journal of Combinatorics
ISSN
1077-8926
e-ISSN
—
Volume of the periodical
26
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
28
Pages from-to
1-28
UT code for WoS article
000463559900011
EID of the result in the Scopus database
—