Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BOKAL Drago DVOŘÁK Zdeněk HLINĚNÝ Petr LEANOS Jesus MOHAR Bojan WIEDERA Tilo

Year of publication 2019
Type Article in Proceedings
Conference 35th International Symposium on Computational Geometry, SoCG 2019
MU Faculty or unit

Faculty of Informatics

Citation
Web open access
Doi http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14
Keywords Crossing number; Crossing-critical; Exhaustive generation; Path-width
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info