On Universal Positive Graphs

2023

Закрытый доступ Метаданные (CSL-JSON)
DOI 10.1134/s003744662301010x
Достоверность данных 70 средняя
Как считается эта оценка

Складывается из проверяемых признаков самой записи: есть ли у статьи DOI, сколько независимых источников подтвердили её данные, заполнены ли обязательные поля и насколько свежо последнее подтверждение. Снижают оценку расхождения между источниками и отсутствие идентификатора. Значение от 80 означает, что запись опубликована без дополнительной проверки; от 60 до 79 — что она опубликована с пониженной достоверностью и ручная проверка желательна. Запись, выверенную редактором вручную, пересчёт не опускает ниже 90. Это оценка наших данных о статье, а не оценка самой статьи.

Аннотация

We study the existence of the universal computable numberings and the universal graphs for various classes of positive graphs. It is known that each $ \forall $ -axiomatizable class of graphs $ K $ can be characterized as follows: A graph $ G $ belongs to $ K $ if and only if for a given family of finite graphs $ \mathbf{F} $ no graph in $ \mathbf{F} $ is isomorphically embeddable into $ G $ .If all graphs in $ \mathbf{F} $ are weakly connected; then, under additional effectiveness conditions, the corresponding class $ K $ has some universal computable numbering and universal positive graph. The effectiveness conditions hold for forests, bipartite graphs, planar graphs, and $ n $ -colorable graphs (for a fixed number $ n $ ). If $ \mathbf{F} $ is a finite family of the graphs with weakly connected complement then the corresponding class $ K $ contains a universal positive graph (in general, a universal computable numbering for $ K $ may fail to exist).