Complexity Estimation for the Coloring of Graphs on a Turing Machine

The paper presents a discussion of $c$-graphs, i.e., undirected graphs having neither loops nor multiple edges with numbered vertices and having $c$ times as many edges as vertices. As already proved by the author in [Latv. Mat. Ezhegodnik, vol. 7, Riga: Zinatne, 1970, pp. 111–125], for almost all $c$-graphs $G$ the chromatic number $g(G)$ satisfies the inequality
$$ \frac{c}{\ln c}<\gamma(G)\leq 4c. $$
The object of investigation here is the complexity (in the sense of the number of steps required) of the proper coloring of the vertices of a $c$-graph on a single-head single-tape Turing machine. The complexity of the computerized coloring of a graph for the case in which all information is located in working storage has been analyzed in [A. A. Kalnin'sh, Kibernetika, 1971, no. 4, pp. 103–111]. A graph is naturally encoded on a Turing machine tape as a list of its edges, and the coloring of the graph as a list of colors. Suppose that $k$ is such that almost all $c$-graphs can be $k$-colored; in particular, let it be said that $k=4c$. It is proved that for any Turing machine properly $k$-coloring almost all $c$-graphs at least $n^2\log n$ steps in order of magnitude are required for almost all $c$-graphs, where n is the number of vertices of the graph. On the other hand, it is shown that almost all c-graphs can be colored on a Turing machine by no more than $4c$ colors in an order of $n^2\log^2n$ steps.