Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c ≤ 12

DC FieldValueLanguage
dc.contributor.authorBokal, Drago
dc.contributor.authorDvorak, Zdenek
dc.contributor.authorHlineny, Petr
dc.contributor.authorLeanos, Jesus
dc.contributor.authorMohar, Bojan
dc.contributor.authorWiedera, Tilo
dc.date.accessioned2024-01-04T10:37:53Z-
dc.date.available2024-01-04T10:37:53Z-
dc.date.issued2022
dc.identifier.issn0209-9683
dc.identifier.urihttp://osnascholar.ub.uni-osnabrueck.de/handle/unios/73300-
dc.description.abstractWe 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 arbitrarily many vertices 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 Dvorak and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <= 12.(1)
dc.description.sponsorshipARRS [J1-8130, J1-2452, P1-0297]; Czech Science Foundation [17-04611S, 17-00837S, 20-04567S]; PFCE-UAZ 2018-2019 grant; NSERC Discovery Grant (Canada) [R611450]; Canada Research Chairs program; ARRS (Slovenia) [J1-8130, J1-2452]; German Research Foundation (DFG) [CH 897/2-2]; Drago Bokal was supported by ARRS Projects J1-8130, J1-2452 and ARRS Programme P1-0297.; Zdenek Dvorak was supported by project 17-04611S (Ramsey-like aspects of graph coloring) of Czech Science Foundation.; Petr Hlineny was supported by projects 17-00837S and 20-04567S of Czech Science Foundation.; Jesus Leanos was partially supported by PFCE-UAZ 2018-2019 grant.; Bojan Mohar was supported in part by the NSERC Discovery Grant R611450 (Canada), by the Canada Research Chairs program, and by the Research Projects J1-8130 and J1-2452 of ARRS (Slovenia).; Tilo Wiedera was supported by the German Research Foundation (DFG) project CH 897/2-2.
dc.language.isoen
dc.publisherSPRINGER HEIDELBERG
dc.relation.ispartofCOMBINATORICA
dc.subject05C10
dc.subjectADDITIVITY
dc.subjectINFINITE FAMILIES
dc.subjectMathematics
dc.subjectNUMBER
dc.titleBounded Degree Conjecture Holds Precisely for <i>c</i>-Crossing-Critical Graphs with <i>c</i> ≤ 12
dc.typejournal article
dc.identifier.doi10.1007/s00493-021-4285-3
dc.identifier.isiISI:000780265300003
dc.description.volume42
dc.description.issue5
dc.description.startpage701
dc.description.endpage728
dc.contributor.orcidhttps://orcid.org/0000-0002-8308-9746
dc.contributor.orcidhttps://orcid.org/0000-0003-2125-1514
dc.contributor.researcheridK-5453-2015
dc.contributor.researcheridF-1127-2011
dc.identifier.eissn1439-6912
dc.publisher.placeTIERGARTENSTRASSE 17, D-69121 HEIDELBERG, GERMANY
dcterms.isPartOf.abbreviationCombinatorica
dcterms.oaStatusGreen Published
local.import.remainsaffiliations : University of Maribor; Charles University Prague; Masaryk University Brno; Universidad Autonoma de Zacatecas; Simon Fraser University; University Osnabruck
local.import.remainsearlyaccessdate : MAR 2022
local.import.remainsweb-of-science-index : Science Citation Index Expanded (SCI-EXPANDED)
Show simple item record

Page view(s)

2
Last Week
0
Last month
0
checked on Jul 16, 2024

Google ScholarTM

Check

Altmetric