Publication details

On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees



Year of publication 2021
Type Article in Proceedings
Conference Extended Abstracts EuroComb 2021. Trends in Mathematics
MU Faculty or unit

Faculty of Informatics

Keywords Graph; Crossing number; Crossing-critical families
Description A surprising result of Bokal et al. proved that the exact minimum value of c such that c-crossing-critical graphs do not have bounded maximum degree is c=13. The key to the result is an inductive construction of a family of 13-crossing-critical graphs with many vertices of arbitrarily high degrees. While the inductive part of the construction is rather easy, it all relies on the fact that a certain 17-vertex base graph has the crossing number 13, which was originally verified only by a machine-readable computer proof. We now provide a relatively short self-contained computer-free proof.
Related projects:

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

More info