Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12

2019/03/13 by Bokal, Drago, Dvořák, Zdeněk, Hliněný, Petr +3
#Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1903.05363

Abstract

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 Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c≤ 12.

Related

• On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees
• Structure and generation of crossing-critical graphs
• Technical details regarding infinite families of crossing-critical graphs with prescribed average degree and crossing number
• On Degree Properties of Crossing-Critical Families of Graphs
• Infinite families of crossing-critical graphs with prescribed average degree and crossing number