Разрешимость универсальных теорий и аксиоматизируемость наследственных классов графов

В данной работе методами теории моделей изучаются наследственные классы графов, определенные в терминах запрещенных непорожденных подграфов. Рассмотрены вопросы универсальной аксиоматизируемости и рекурсивной аксиоматизируемости наследственных классов графов. Показано, что наследственный класс графов универсально аксиоматизируем тогда и только тогда, когда он может быть определен в терминах конечных запрещенных подграфов. Доказана разрешимость универсальной теории графов и универсальной теории произвольного рекурсивно аксиоматизируемого наследственного класса графов.