Informace o projektu
Planar graph emulators
Kód projektu | MUNI/C/0883/2010 CEP CORDIS MU WEB INET MU |
---|---|
Doba řešení | 01.01.2011–31.12.2011 |
Stav | ukončený |
Investor | Masarykova univerzita |
Program | Grantová agentura MU |
Řešitel za FI |
Anotace
Projekt se pohybuje v oblasti teorie grafů a zabývá se problémem existence konečných rovinných emulátorů pro neprojektivní grafy. Podle hypotézy M. Fellowse (1985) takové emulátory neexistují. Tato hypotéza byla ale na konci roku 2008 překvapivě vyvrácena. Po více než 20 letech se tedy toto pole se otevřelo pro nový výzkum. Řešitel projektu ve své bakalářské práci ukázal, že existuje pouze konečná množina důležitých neprojektivních grafů, které mají konečný rovinný emulátor a zároveň neobsahují ani jeden z 6 problematických minorů. Projekt navazuje na předchozí výzkum a klade si za cíl prohloubit a následně publikovat dosažené výsledky.