Other formats:
BibTeX
LaTeX
RIS
@article{2243995,
author = {Bokal, Drago and Dvořák, Zdeněk and Hliněný, Petr and Leanos, Jesus and Mohar, Bojan and Wiedera, Tilo},
article_location = {GERMANY},
article_number = {5},
doi = {http://dx.doi.org/10.1007/s00493-021-4285-3},
keywords = {Crossing number; Crossing-critical; Exhaustive generation; Path-width},
language = {eng},
issn = {0209-9683},
journal = {COMBINATORICA},
title = {Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12},
url = {http://dx.doi.org/10.1007/s00493-021-4285-3},
volume = {42},
year = {2022}
}
TY - JOUR
ID - 2243995
AU - Bokal, Drago - Dvořák, Zdeněk - Hliněný, Petr - Leanos, Jesus - Mohar, Bojan - Wiedera, Tilo
PY - 2022
TI - Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12
JF - COMBINATORICA
VL - 42
IS - 5
SP - 701-728
EP - 701-728
PB - SPRINGER HEIDELBERG
SN - 02099683
KW - Crossing number
KW - Crossing-critical
KW - Exhaustive generation
KW - Path-width
UR - http://dx.doi.org/10.1007/s00493-021-4285-3
N2 - We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c >= 13 and d >= 1, we give first explicit constructions of c-crossing-critical graphs containing a vertex of degree greater than d. We also show that such unbounded degree constructions do not exist for c <=12, precisely, that there exists a constant D such that every c-crossing-critical graph with c <=12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvorák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.
ER -
BOKAL, Drago, Zdeněk DVOŘÁK, Petr HLINĚNÝ, Jesus LEANOS, Bojan MOHAR and Tilo WIEDERA. Bounded degree conjecture holds precisely for c-crossing-critical graphs with c\&{}lt;=12. \textit{COMBINATORICA}. GERMANY: SPRINGER HEIDELBERG, 2022, vol.~42, No~5, p.~701-728. ISSN~0209-9683. Available from: https://dx.doi.org/10.1007/s00493-021-4285-3.
|
