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

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr KORBELA Michal

Year of publication 2019
Type Article in Periodical
Magazine / Source Acta Math. Univ. Comenianae
MU Faculty or unit

Faculty of Informatics

Citation
Web http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1178/725
Keywords graph; crossing number; crossing-critical
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.