Další formáty:
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 a Tilo WIEDERA. Bounded degree conjecture holds precisely for c-crossing-critical graphs with c\&{}lt;=12. \textit{COMBINATORICA}. GERMANY: SPRINGER HEIDELBERG, 2022, roč.~42, č.~5, s.~701-728. ISSN~0209-9683. Dostupné z: https://dx.doi.org/10.1007/s00493-021-4285-3.
|