Forbidden subgraphs and forbidden substructures

Decidability of theories and sets of sentences (03B25) Model theory of denumerable and separable structures (03C15) Models of other mathematical theories (03C65) Undecidability and degrees of sets of sentences (03D35) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

Cites work

Cited in

(35)

This page was built for publication: Forbidden subgraphs and forbidden substructures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2758062)