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.

Basic information

Original name

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

Authors

BOKAL, Drago (705 Slovenia), Zdeněk DVOŘÁK (203 Czech Republic), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution), Jesus LEANOS (484 Mexico), Bojan MOHAR (705 Slovenia) and Tilo WIEDERA (276 Germany)

Edition

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

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

References:

DOI open access preprint

Impact factor

Impact factor: 1.100

RIV identification code

RIV/00216224:14330/22:00129305

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1007/s00493-021-4285-3

UT WoS

000780265300003

Keywords in English

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

Abstract

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.

Links

GA20-04567S, research and development project

Name: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Czech Science Foundation

Citovat

BOKAL, Drago, Zdeněk DVOŘÁK, Petr HLINĚNÝ, Jesus LEANOS, Bojan MOHAR and Tilo WIEDERA. Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12. COMBINATORICA. GERMANY: SPRINGER HEIDELBERG, 2022, vol. 42, No 5, p. 701-728. ISSN 0209-9683. Available from: https://dx.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 = {http://dx.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 and Tilo WIEDERA. Bounded degree conjecture holds precisely for c-crossing-critical graphs with c\&{}lt;=12. \textit{COMBINATORICA}. GERMANY: SPRINGER HEIDELBERG, 2022, vol.~42, No~5, p.~701-728. ISSN~0209-9683. Available from: https://dx.doi.org/10.1007/s00493-021-4285-3.

Detailed Information on Publication Record