On universal positive graphs
B. S. Kalmurzaevab,
N. A. Bazhenovc,
D. B. Alisha a Al-Farabi Kazakh National University
b Kazakh-British Technical University
c Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
Abstract:
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).
Keywords:
computable reducibility, computable numbering, computably enumerable relation, positive graph.
UDC:
510.53 Received: 06.04.2022
Revised: 07.07.2022
Accepted: 15.08.2022
DOI:
10.33048/smzh.2023.64.110