On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees

HLINĚNÝ, Petr a Michal KORBELA. On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees. In Nešetřil J., Perarnau G., Rué J., Serra O. Extended Abstracts EuroComb 2021. Trends in Mathematics. Cham: Birkhäuser, 2021, s. 50-56. ISBN 978-3-030-83822-5. Dostupné z: https://dx.doi.org/10.1007/978-3-030-83823-2_9.

Základní údaje

Originální název

On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Michal KORBELA (703 Slovensko, domácí)

Vydání

Cham, Extended Abstracts EuroComb 2021. Trends in Mathematics, od s. 50-56, 7 s. 2021

Nakladatel

Birkhäuser

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Kód RIV

RIV/00216224:14330/21:00119292

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-83822-5

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-83823-2_9

Klíčová slova anglicky

Graph; Crossing number; Crossing-critical families

Štítky

formela-conference

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

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.

---

Návaznosti

GA20-04567S, projekt VaV	Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs
MUNI/A/1108/2020, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Akronym: SV-FI MAV X.) Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X.