Detailed Information on Publication Record
2021
On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees
HLINĚNÝ, Petr and Michal KORBELABasic information
Original name
On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees
Authors
HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution) and Michal KORBELA (703 Slovakia, belonging to the institution)
Edition
Cham, Extended Abstracts EuroComb 2021. Trends in Mathematics, p. 50-56, 7 pp. 2021
Publisher
Birkhäuser
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Switzerland
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
printed version "print"
References:
RIV identification code
RIV/00216224:14330/21:00119292
Organization unit
Faculty of Informatics
ISBN
978-3-030-83822-5
ISSN
Keywords in English
Graph; Crossing number; Crossing-critical families
Tags
Tags
International impact, Reviewed
Změněno: 28/4/2022 10:05, RNDr. Pavel Šmerk, Ph.D.
Abstract
V originále
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.
Links
| GA20-04567S, research and development project |
| ||
| MUNI/A/1108/2020, interní kód MU |
|