J 2015

Planar Emulators Conjecture Is Nearly True for Cubic Graphs

DERKA, Martin a Petr HLINĚNÝ

Základní údaje

Originální název

Planar Emulators Conjecture Is Nearly True for Cubic Graphs

Autoři

DERKA, Martin (203 Česká republika, domácí) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

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

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Nizozemské království

Utajení

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

Impakt faktor

Impact factor: 0.650

Kód RIV

RIV/00216224:14330/15:00080608

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000355041300007

Klíčová slova anglicky

planar emulator; projective planar graph; graph minor

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 30. 3. 2016 09:43, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

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.

Česky

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

Návaznosti

GBP202/12/G061, projekt VaV
Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)
Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky