Publication at Faculty of Mathematics and Physics |
2010
Abstract
We provide two new combinatorial versions of the CSP dichotomy classification conjecture. As with our previous version of the fibre construction, we are able to address restricted versions of the dichotomy conjecture.
In particular, we reduce the Feder-Hell-Huang conjecture to the CSP dichotomy classification conjecture, and we prove the Kostochka-Nesetril-Smolikova conjecture. Although these results were proved independently by Jonsson et al. and Kun respectively, we give different, shorter, proofs.