J 2025

On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees

HLINĚNÝ, Petr a Michal KORBELA

Základní údaje

Originální název

On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees

Autoři

HLINĚNÝ, Petr ORCID a Michal KORBELA

Vydání

DISCRETE MATHEMATICS, NETHERLANDS, ELSEVIER, 2025, 0012-365X

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

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

Odkazy

Impakt faktor

Impact factor: 0.900 v roce 2024

Označené pro přenos do RIV

Ano

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

EID Scopus

Klíčová slova anglicky

Graph; Crossing number; Crossing-critical families

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 18. 3. 2026 23:09, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

A recent result of Bokal et al. (2022) [3] 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 another long-standing 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.