Publication at Faculty of Mathematics and Physics |
2008
Abstract
We use a connection between polymorphisms and the structure of smooth digraphs to prove the conjecture of Bang-Jensen and Hell from 1990 and, as a consequence, a conjecture of Bang-Jensen, Hell and MacGillivray from 1995. The conjectured characterization of computationally complex coloring problems for smooth digraphs is proved using tools of universal algebra.
We cite further graph results obtained using this new approach. The proofs are based in an universal algebraic framework developed for the Constraint Satisfaction Problem and the CSP dichotomy conjecture of Feder and Vardi in particular.