Zde se nacházíte:
Informace o publikaci
On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees
Autoři | |
---|---|
Rok publikování | 2021 |
Druh | Článek ve sborníku |
Konference | Extended Abstracts EuroComb 2021. Trends in Mathematics |
Fakulta / Pracoviště MU | |
Citace | |
www | http://arxiv.org/abs/2105.01104 |
Doi | http://dx.doi.org/10.1007/978-3-030-83823-2_9 |
Klíčová slova | Graph; Crossing number; Crossing-critical families |
Popis | 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. |
Související projekty: |