Geodesic
Decidability of universal theories and axiomatizability of hereditary classes of graphs
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 1, pp. 100-111

Voir la notice de l'article provenant de la source Math-Net.Ru

Hereditary classes of graphs defined by forbidden non-induced subgraphs are studied by model theory methods. Problems of universal axiomatizability and recursive axiomatizability of hereditary classes of graphs are considered. It is shown that a hereditary class of graphs is universally axiomatizable if and only if it can be defined in terms of finite forbidden subgraphs. It is proved that the universal theory of graphs and the universal theory of any recursive axiomatizable hereditary class of graphs are decidable.
Keywords: hereditary class of graphs, universal theory, universal axiomatizability, decidability. 
@article{TIMM_2016_22_1_a10,
     author = {A. V. Il'ev},
     title = {Decidability of universal theories and axiomatizability of hereditary classes of graphs},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {100--111},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2016_22_1_a10/}
}
TY  - JOUR
AU  - A. V. Il'ev
TI  - Decidability of universal theories and axiomatizability of hereditary classes of graphs
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2016
SP  - 100
EP  - 111
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2016_22_1_a10/
LA  - ru
ID  - TIMM_2016_22_1_a10
ER  - 
%0 Journal Article
%A A. V. Il'ev
%T Decidability of universal theories and axiomatizability of hereditary classes of graphs
%J Trudy Instituta matematiki i mehaniki
%D 2016
%P 100-111
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2016_22_1_a10/
%G ru
%F TIMM_2016_22_1_a10
A. V. Il'ev. Decidability of universal theories and axiomatizability of hereditary classes of graphs. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 1, pp. 100-111. http://geodesic.mathdoc.fr/item/TIMM_2016_22_1_a10/