Planar Emulators Conjecture Is Nearly True for Cubic Graphs

Investor logo

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

DERKA Martin HLINĚNÝ Petr

Year of publication 2015
Type Article in Periodical
Magazine / Source European Journal of Combinatorics
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1016/j.ejc.2015.02.009
Field General mathematics
Keywords planar emulator; projective planar graph; graph minor
Description We prove that a cubic nonprojective graph cannot have a finite planar emulator, unless it belongs to one of two very special cases (in which the answer is open). This shows that Fellows' planar emulator conjecture, disproved for general graphs by Rieck and Yamashita in 2008, is nearly true on cubic graphs, and might very well be true there definitely.
Related projects:

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