A combinatorial constraint satisfaction problem dichotomy classification conjecture
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F10%3A10081048" target="_blank" >RIV/00216208:11320/10:10081048 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A combinatorial constraint satisfaction problem dichotomy classification conjecture
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2010
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
European Journal of Combinatorics
ISSN
0195-6698
e-ISSN
—
Volume of the periodical
31
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
17
Pages from-to
—
UT code for WoS article
000271971000024
EID of the result in the Scopus database
—