Graphs, Polymorphisms and the Complexity of Homomorphism Problems

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00207284" target="_blank" >RIV/00216208:11320/08:00207284 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Graphs, Polymorphisms and the Complexity of Homomorphism Problems
Original language description
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 characterizationof 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.
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proccedings of the 40th ACM Symposium on Theory of Computing, STOC´08
ISBN
978-1-60558-047-0
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
—
Publisher name
ACM Kanada
Place of publication
Kanada
Event location
Kanada
Event date
Jan 1, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000266622800085

Similar results(10)