Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334287 | Theoretical Computer Science | 2005 | 9 Pages |
Abstract
The H-Coloring problem can be expressed as a particular case of the constraint satisfaction problem (CSP) whose computational complexity has been intensively studied under various approaches in the last several years. We show that the dichotomy theorem proved by Hell and NeÅ¡etÅil [On the complexity of H-coloring, J. Combin. Theory Ser. B 48 (1990) 92-110] for the complexity of the H-Coloring problem for undirected graphs can be obtained using general methods for studying CSP, and that the criterion distinguishing the tractable cases of the H-Coloring problem agrees with that conjectured in [A.A. Bulatov, P.G. Jeavons, A.A. Krokhin, Constraint satisfaction problems and finite algebras, in: Proc. 27th Internat. Colloq. on Automata, Languages and Programming-ICALP'00, Lecture Notes in Computer Science, Vol. 1853, Springer, Berlin, 2000, pp. 272-282] for the complexity of the general CSP.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andrei A. Bulatov,