Forbidden subgraphs and forbidden substructures
Gregory L. Cherlin, Niandong Shi · Journal of Symbolic Logic · 2001
Abstract The problem of the existence of a universal structure omitting a finite set of forbidden substructures is reducible to the corresponding problem in the category of graphs with a vertex coloring by two colors. It is not known whether this problem reduces further to the category of ordinary graphs. It is also not known whether these problems are decidable.