Decidability of universal theories and axiomatizability of hereditary classes of graphs

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.