Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c ≤ 12

Autor(en): Bokal, Drago
Dvorak, Zdenek
Hlineny, Petr
Leanos, Jesus
Mohar, Bojan
Wiedera, Tilo
Stichwörter: 05C10; ADDITIVITY; INFINITE FAMILIES; Mathematics; NUMBER
Erscheinungsdatum: 2022
Herausgeber: SPRINGER HEIDELBERG
Enthalten in: COMBINATORICA
Band: 42
Ausgabe: 5
Startseite: 701
Seitenende: 728
Zusammenfassung: 
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 arbitrarily many vertices 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 Dvorak and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <= 12.(1)
ISSN: 0209-9683
DOI: 10.1007/s00493-021-4285-3

Show full item record

Page view(s)

1
Last Week
0
Last month
0
checked on Jun 17, 2024

Google ScholarTM

Check

Altmetric