Informace o publikaci

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

Autoři

DVOŘÁK Zdeněk HLINĚNÝ Petr MOHAR Bojan BOKAL Drago LEANOS Jesus 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
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.

Další info