A combinatorial constraint satisfaction problem dichotomy classification conjecture

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A combinatorial constraint satisfaction problem dichotomy classification conjecture

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

A combinatorial constraint satisfaction problem dichotomy classification conjecture

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2010

Kód důvěrnosti údajů

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

Název periodika

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

31

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

17

Strana od-do

—

Kód UT WoS článku

000271971000024

EID výsledku v databázi Scopus

—