Forbidden subgraphs and forbidden substructures (Q2758062)

For a finite set \(\mathcal C\) of finite structures in a finite relational language \(L\), the following problem is considered. Let \(K\) be the class of all countable \(L\)-structures which do not embed any structure in \(\mathcal C\). Is there a universal structure in \(K\), that is, a structure in \(K\) which embeds any structure in \(K\)? Here one can consider embeddings either as strong embeddings (that is, preserving both \(L\)-relations and negated \(L\)-relations) or as weak embeddings (that is, preserving only \(L\)-relations); so there are two slightly different questions. Earlier the problem was considered for various classes of graphs with forbidden subgraphs. Usually there is no universal graph of the desired type; however, for some sets of forbidden subgraphs the existence of a universal graph had been proven. The authors consider the following decision problem: for any \(L\) and \(\mathcal C\), determine whether \(K\) has a universal structure. The main result of the paper is that the decision problem is equivalent to the corresponding problem in the category of graphs with a vertex coloring by two colors. Moreover, the decision problems for strong and weak embeddings are shown to be equivalent. It is not known whether the problem reduces further to the category of ordinary graphs. It is also not known whether these problems are decidable; the authors feel that they may well be undecidable.