Publication |
2006
Abstract
We prove that there exists a constant $k$ such that for every $n \geq 1$ there exists a directed core graph $H_n$ with at least $2^n$ vertices such that a directed graph $G$ is $H_n$-colorable if and only if every subgraph of $G$ with at most $kn\log(n)$ vertices is $H_n$-colorable. Our examples show that in general the 'duals of relational structures' in the sense of [J.
Nesetril and C. Tardif, J.
Combin. Theory Ser.
B, 80 (2000), pp. 80-97] can have superpolynomial size. The construction given in this paper gives a double exponential upper bound for such a construction.
Here we improve this to an exponential upper bound.