On the achievable average degrees in 2-crossing-critical graphs

Varování

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

HLINĚNÝ Petr KORBELA Michal

Rok publikování 2019
Druh Článek v odborném periodiku
Časopis / Zdroj Acta Math. Univ. Comenianae
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1178/725
Klíčová slova graph; crossing number; crossing-critical
Popis c-Crossing-critical graphs are the minimal graphs requiring at least c edge crossings in every drawing in the plane. The structure of these obstructions is very rich for every c>=2. Although, at least in the first nontrivial case of c=2, their structure is well understood. For example, we know that, aside of finitely many small exceptions, the 2-crossing-critical graphs have vertex degrees from the set {3, 4, 5, 6} and their average degree can achieve exactly all rational values from the interval [3+1/2 , 4+2/3]. Continuing in depth in this research direction, we determine which average degrees of 2-crossing-critical graphs are possible if we restrict their vertex degrees to proper subsets of {3, 4, 5, 6}. In particular, we identify the (surprising) subcases in which, by number-theoretical reasons, the achievable average degrees form discontinuous sets of rationals.
Související projekty:

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