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

Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

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

Rok publikování 2019
Druh Článek ve sborníku
Konference 35th International Symposium on Computational Geometry, SoCG 2019
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www open access
Doi http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14
Klíčová slova Crossing number; Crossing-critical; Exhaustive generation; Path-width
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.