. "11320" . . "369610" . "Graphs; Polymorphisms; Complexity; Homomorphism; Problems"@en . "Graphs, Polymorphisms and the Complexity of Homomorphism Problems"@en . "Kozik, Marcin" . "RIV/00216208:11320/08:00207284!RIV10-GA0-11320___" . "Kozik, Marcin" . . . . . "P(GA201/06/0664), P(LC505), Z(MSM0021620839)" . . . "Niven, Todd" . . "Niven, Todd" . . "8"^^ . "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."@en . "Proccedings of the 40th ACM Symposium on Theory of Computing, STOC\u00B408" . "978-1-60558-047-0" . . . "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." . "[C1AB36B1DCB9]" . . "RIV/00216208:11320/08:00207284" . . . "Graphs, Polymorphisms and the Complexity of Homomorphism Problems" . . "Barto, Libor" . . "2008-01-01+01:00"^^ . "Graphs, Polymorphisms and the Complexity of Homomorphism Problems"@en . "000266622800085" . "Kanada" . "Kanada" . . . . "ACM Kanada" . "3"^^ . "Graphs, Polymorphisms and the Complexity of Homomorphism Problems" . . "3"^^ .