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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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},
     year = {2016},
     volume = {22},
     number = {1},
     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
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
%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/

[1] Gorbunov V.A., Algebraicheskaya teoriya kvazimnogoobrazii, Nauch. kn., Novosibirsk, 1999, 368 pp.

[2] Distel R., Teoriya grafov, Izd-vo In-ta matematiki, Novosibirsk, 2002, 336 pp.

[3] Zykov A.A., Osnovy teorii grafov, Nauka, M., 1987, 384 pp. | MR

[4] Ershov Yu.L., Problemy razreshimosti i konstruktivnye modeli, Nauka, M., 1980, 416 pp. | MR

[5] Ershov Yu.L., Palyutin E.A., Matematicheskaya logika, Nauka, M., 1987, 336 pp. | MR

[6] Lavrov I.A., “Effektivnaya neotdelimost mnozhestva tozhdestvenno istinnykh i mnozhestva konechno oproverzhimykh formul nekotorykh elementarnykh teorii”, Algebra i logika, 2:1 (1963), 5–18 | MR | Zbl

[7] Malyshev D.S., “Kriticheskie klassy grafov dlya zadachi o rebernom spiskovom ranzhirovanii”, Diskret. analiz i issled. operatsii, 20:5 (2013), 59–76 | MR | Zbl

[8] Maltsev A.I., “Universalno aksiomatiziruemye podklassy lokalno konechnykh klassov modelei”, Sib. mat. zhurn., 1967, no. 5, 1005–1014 | Zbl

[9] Uilson R., Vvedenie v teoriyu grafov, Mir, M., 1977, 208 pp. | MR

[10] Yu.L. Ershov, I.A. Lavrov, A.D. Taimanov, M.A. Taitslin, “Elementarnye teorii”, Uspekhi mat. nauk, 20:4 (1965), 37–108 | MR | Zbl

[11] Bozapalidis A., Kalampakas A., “An axiomatization of graphs”, Acta inform., 41:1 (2004), 19–61 | DOI | MR | Zbl

[12] Caicedo X., “Finitely axiomatizable quasivarieties of graphs”, Algebra Universalis, 34:2 (1995), 314–321 | DOI | MR | Zbl

[13] M. Yamamoto, S. Nishizaki, M. Hagiya, Y. Toda, “Formalization of planar graphs”, 8th Int. Workshop on Higer Order Logic, Theorem Proving and Its Applications, Lecture Notes in Comput. Sci., 971, Springer, Berlin, 1995, 369–384 | DOI | MR | Zbl

[14] Razborov A.A., “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282 | DOI | MR | Zbl

[15] Tarski A., “Contributions to the theory of models I”, Nederl. Akad. Wetensch. Proc. Ser. A., Indagationes Math., 16 (1954), 572-581 ; “Contributions to the theory of models II”, 582-583 | DOI | MR | MR

[16] Taylor W., “Atomic compactness and graph theory”, Fund. Math., 65 (1969), 139–145 | MR | Zbl