On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees

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

HLINĚNÝ Petr KORBELA Michal

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

Faculty of Informatics

Citation
Web http://arxiv.org/abs/2105.01104
Doi http://dx.doi.org/10.1007/978-3-030-83823-2_9
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