On Universal Positive Graphs

Kalmurzaev B.S. Bazhenov N.A. Alish D.B.
January 2023 Pleiades Publishing

Siberian Mathematical Journal
2023 #64 Issue 1 83 - 93 pp.

We study the existence of the universal computable numberings andthe universal graphs for various classes of positive graphs. It is known thateach $ 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 universalcomputable numbering and universal positive graph.The effectiveness conditions hold forforests, bipartite graphs,planar graphs, and $ n $-colorable graphs (for a fixed number $ n $). If $ mathbf{F} $ isa finite family of the graphs with weakly connected complement then the correspondingclass $ K $ contains a universal positive graph (in general, a universal computable numberingfor $ K $ may fail to exist).

510.53 , computable numbering , computable reducibility , computably enumerable relation , positive graph

Text of the article Перейти на текст статьи

Al-Farabi Kazakh National University, Almaty, Kazakhstan
Sobolev Institute of Mathematics, Novosibirsk, Russian Federation
Kazakh–British National University, Almaty, Kazakhstan

Al-Farabi Kazakh National University
Sobolev Institute of Mathematics
Kazakh–British National University

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026