D 2013

Planar Emulators Conjecture Is Nearly True for Cubic Graphs

HLINĚNÝ, Petr a Martin DERKA

Základní údaje

Originální název

Planar Emulators Conjecture Is Nearly True for Cubic Graphs

Název česky

Hypotéza rovinných emulátorů je skoro pravdivá na kubických grafech

Autoři

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

Vydání

Pisa, Italy, The Seventh European Conference on Combinatorics, Graph Theory and Applications - Eurocomb 2013, od s. 245-250, 6 s. 2013

Nakladatel

Scuola Normale Superiore Pisa

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Itálie

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

Kód RIV

RIV/00216224:14330/13:00066368

Organizační jednotka

Fakulta informatiky

ISBN

978-88-7642-474-8

Klíčová slova anglicky

planar cover; planar emulator; projective planar; splitter theorem

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 21. 11. 2013 17:40, 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 one of two very special cases happen (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

Dokazujeme, že neprojektivní kubický graf nemůže mít rovinný emulátor až na dva speciální případy. Tím hypotéza emulátorů, obecně vyvrácená v 2008, je naopak téměř dokázána v tomto speciálním případě.

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
MUNI/A/0739/2012, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/0760/2012, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Akronym: FI MAV II.)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty