Оценка сложности раскраски графов на машине Тьюринга

Рассматриваются $c$-графы – неориентированные графы, без петель и кратных ребер с нумерованными вершинами, число ребер в которых в $c$ раз больше числа вершин. Как уже доказано автором [1], почти для всех $c$-графов $G$ хроматическое число $\gamma(G)$ удовлетворяет неравенству
$$ \frac{c}{\ln c}<\gamma(G)\leq 4c. $$
В этой работе исследуется сложность (в смысле числа шагов) правильной раскраски вершин $c$-графа на одноголовочной одноленточной машине Тьюринга. Сложность раскраски графов на ЭВМ в случае, когда вся информация помещается в оперативной памяти, была исследована в [2]. Граф на ленте машины Тьюринга кодируется естественным образом как список его ребер, а раскраска графа – как список цветов. Пусть $k$ – такое, что почти все $c$-графы можно раскрасить к цветами, в частности можно взять $k=4c$. Доказано, что при любой машине Тьюринга, правильно раскрашивающей почти все $c$-графы к цветами, почти для всех $c$-графов требуется по порядку не менее $n^2\log n$ шагов, где $п$ – число вершин графа. С другой стороны, показано, что почти все $c$-графы можно раскрасить на машине Тьюринга не более чем $4c$ цветами, используя по порядку $n^2\log^2n$ шагов.