On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees

Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

HLINĚNÝ Petr KORBELA Michal

Rok publikování 2021
Druh Článek ve sborníku
Konference Extended Abstracts EuroComb 2021. Trends in Mathematics
Fakulta / Pracoviště MU

Fakulta informatiky

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.