J 2015

Planar Emulators Conjecture Is Nearly True for Cubic Graphs

DERKA, Martin and Petr HLINĚNÝ

Basic information

Original name

Planar Emulators Conjecture Is Nearly True for Cubic Graphs

Authors

DERKA, Martin (203 Czech Republic, belonging to the institution) and Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution)

Edition

European Journal of Combinatorics, Elsevier, 2015, 0195-6698

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10101 Pure mathematics

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

Impact factor

Impact factor: 0.650

RIV identification code

RIV/00216224:14330/15:00080608

Organization unit

Faculty of Informatics

UT WoS

000355041300007

Keywords in English

planar emulator; projective planar graph; graph minor

Tags

International impact, Reviewed
Změněno: 30/3/2016 09:43, prof. RNDr. Petr Hliněný, Ph.D.

Abstract

V originále

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.

In Czech

Dokážeme, že již obecně vyvrácená Fellowsova hypotéza o rovinných emulátorech je téměř pravdivá pro kubické grafy.

Links

GBP202/12/G061, research and development project
Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)
Investor: Czech Science Foundation