Publikace |
2006
Abstrakt
Dokazujeme, že existuje konstanta k taková, že pro každé $n \geq 1$ existuje orientovaný core graf $H_n$ s alespoň $2^n$ vrcholy takový, že orientovaný graf $G$ je $H_n$-obarvitelný pravě když každý podgraf $G$ s nejvýše $kn\log(n)$ vrcholy je $H_n$ obarvitelný. Naše příklady ukazují, že 'duály relačních struktur' ve smyslu [J.
Nešetřil a C. Tardif, J.
Combin. Theory Ser.
B, 80 (2000), pp. 80-97] mohou obecně mít superpolynomiální velikost. Konstrukce v tom článku dává dvojitě exponenciální horní odhad na takovou konstrukci.
Zde tento odhad vylepšíme na exponenciální.