Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2105.01104 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913249052590080 |
|---|---|
| author | Hliněný, Petr Korbela, Michal |
| author_facet | Hliněný, Petr Korbela, Michal |
| contents | A recent result of Bokal et al. [Combinatorica, 2022] 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 that 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 provide a relatively short self-contained computer-free proof of the latter fact. Furthermore, we subsequently generalize the critical construction in order to provide a definitive answer to a remaining open question of this research area; we prove that for every c>=13 and integers d,q, there exists a c-crossing-critical graph with more than q vertices of each of the degrees 3,4,...,d. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_01104 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees Hliněný, Petr Korbela, Michal Combinatorics A recent result of Bokal et al. [Combinatorica, 2022] 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 that 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 provide a relatively short self-contained computer-free proof of the latter fact. Furthermore, we subsequently generalize the critical construction in order to provide a definitive answer to a remaining open question of this research area; we prove that for every c>=13 and integers d,q, there exists a c-crossing-critical graph with more than q vertices of each of the degrees 3,4,...,d. |
| title | On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2105.01104 |