Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1799163,
author = {Hliněný, Petr and Korbela, Michal},
address = {Cham},
booktitle = {Extended Abstracts EuroComb 2021. Trends in Mathematics},
doi = {http://dx.doi.org/10.1007/978-3-030-83823-2_9},
editor = {Nešetřil J., Perarnau G., Rué J., Serra O.},
keywords = {Graph; Crossing number; Crossing-critical families},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Cham},
isbn = {978-3-030-83822-5},
pages = {50-56},
publisher = {Birkhäuser},
title = {On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees},
url = {http://arxiv.org/abs/2105.01104},
year = {2021}
}
TY - JOUR
ID - 1799163
AU - Hliněný, Petr - Korbela, Michal
PY - 2021
TI - On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees
PB - Birkhäuser
CY - Cham
SN - 9783030838225
KW - Graph
KW - Crossing number
KW - Crossing-critical families
UR - http://arxiv.org/abs/2105.01104
N2 - 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.
ER -
HLINĚNÝ, Petr and Michal KORBELA. On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees. In Nešetřil J., Perarnau G., Rué J., Serra O. \textit{Extended Abstracts EuroComb 2021. Trends in Mathematics}. Cham: Birkhäuser, 2021, p.~50-56. ISBN~978-3-030-83822-5. Available from: https://dx.doi.org/10.1007/978-3-030-83823-2\_{}9.
|
