Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
Užitím souvislosti mezi polymorfismy a strkuturou hladkých grafů dokážeme hypotézu Bang-Jensena a Hella z roku 1990 a jako důsledek obdržíme důkaz hypotézy Bang-Jensena, Hella a MacGillivraye z roku 1995. Charakterizace těžkých problémů barvení pro hladké grafy je dokázána nástroji univerzální algebry.
Zmíníme další výsledky o grafech, které byly získány tímto novým přístupem. Důkazy jsou založené na univerzálně algebraických technikách vyvinutých pro problém splnitelnosti omezení a CSP dichotomickou hypotézu Federa a Vardiho.