Bounded degree conjecture holds precisely for
c-crossing-critical graphs with c<=12

J 2022

Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12

BOKAL, Drago; Zdeněk DVOŘÁK; Petr HLINĚNÝ; Jesus LEANOS; Bojan MOHAR et al.

Základní údaje

Originální název

Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12

Autoři

BOKAL, Drago; Zdeněk DVOŘÁK; Petr HLINĚNÝ ; Jesus LEANOS; Bojan MOHAR a Tilo WIEDERA

Vydání

COMBINATORICA, GERMANY, SPRINGER HEIDELBERG, 2022, 0209-9683

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

open access preprint, DOI

Impakt faktor

Impact factor: 1.100

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/22:00129305

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

Crossing number; Crossing-critical; Exhaustive generation; Path-width

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 28. 3. 2023 12:07, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c >= 13 and d >= 1, we give first explicit constructions of c-crossing-critical graphs containing a vertex of degree greater than d. We also show that such unbounded degree constructions do not exist for c <=12, precisely, that there exists a constant D such that every c-crossing-critical graph with c <=12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvorák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.

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

Citovat

BOKAL, Drago; Zdeněk DVOŘÁK; Petr HLINĚNÝ; Jesus LEANOS; Bojan MOHAR a Tilo WIEDERA. Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12. COMBINATORICA. GERMANY: SPRINGER HEIDELBERG, 2022, roč. 42, č. 5, s. 701-728. ISSN 0209-9683. Dostupné z: https://doi.org/10.1007/s00493-021-4285-3.

@article{2243995,
   author = {Bokal, Drago and Dvořák, Zdeněk and Hliněný, Petr and Leanos, Jesus and Mohar, Bojan and Wiedera, Tilo},
   article_location = {GERMANY},
   article_number = {5},
   doi = {https://doi.org/10.1007/s00493-021-4285-3},
   keywords = {Crossing number; Crossing-critical; Exhaustive generation; Path-width},
   language = {eng},
   issn = {0209-9683},
   journal = {COMBINATORICA},
   title = {Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12},
   url = {http://dx.doi.org/10.1007/s00493-021-4285-3},
   volume = {42},
   year = {2022}
}

TY  - JOUR
ID  - 2243995
AU  - Bokal, Drago - Dvořák, Zdeněk - Hliněný, Petr - Leanos, Jesus - Mohar, Bojan - Wiedera, Tilo
PY  - 2022
TI  - Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12
JF  - COMBINATORICA
VL  - 42
IS  - 5
SP  - 701-728
EP  - 701-728
PB  - SPRINGER HEIDELBERG
SN  - 02099683
KW  - Crossing number
KW  - Crossing-critical
KW  - Exhaustive generation
KW  - Path-width
UR  - http://dx.doi.org/10.1007/s00493-021-4285-3
N2  - We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c >= 13 and d >= 1, we give first explicit constructions of c-crossing-critical graphs containing a vertex of degree greater than d. We also show that such unbounded degree constructions do not exist for c <=12, precisely, that there exists a constant D such that every c-crossing-critical graph with c <=12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvorák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.
ER  -

BOKAL, Drago; Zdeněk DVOŘÁK; Petr HLINĚNÝ; Jesus LEANOS; Bojan MOHAR a Tilo WIEDERA. Bounded degree conjecture holds precisely for c-crossing-critical graphs with c\&{}lt;=12. \textit{COMBINATORICA}. GERMANY: SPRINGER HEIDELBERG, 2022, roč.~42, č.~5, s.~701-728. ISSN~0209-9683. Dostupné z: https://doi.org/10.1007/s00493-021-4285-3.

Přehled o publikaci