Forbidden subgraphs and forbidden substructures

Authors
Cherlin, G Shi, ND
Citation
G. Cherlin et Nd. Shi, Forbidden subgraphs and forbidden substructures, J SYMB LOG, 66(3), 2001, pp. 1342-1352
Citations number
6
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF SYMBOLIC LOGIC
ISSN journal
00224812 → ACNP
Volume
66
Issue
3
Year of publication
2001
Pages
1342 - 1352
Database
ISI
SICI code
0022-4812(200109)66:3<1342:FSAFS>2.0.ZU;2-8
Abstract
The problem of the existence of a universal structure omitting a finite set of forbidden substructures is reducible to the corresponding problem in th e 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.