\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.39}{22(3)}{2015}

\usepackage{amsmath, amssymb, amsthm}
\usepackage{amsrefs}
\usepackage{tikz}
\usetikzlibrary{arrows}


% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}



\def\halts{\!\downarrow}
\def\nhalts{\!\uparrow}

\newcommand\N{\mathbb{N}}
\newcommand\NP{\mathrm{NP}}
\newcommand\st{ : }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Finding Domatic Partitions in Infinite Graphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Matthew Jura\\
\small Department of Mathematics\\[-0.8ex]
\small Manhattan College\\[-0.8ex] 
\small 4513 Manhattan College Parkway, Riverdale, NY 10471, USA\\
\small\tt matthew.jura@manhattan.edu\\
\and
Oscar Levin\\
\small School of Mathematical Sciences\\[-0.8ex]
\small University of Northern Colorado\\[-0.8ex]
\small Greeley, CO 80639, USA\\
\small\tt oscar.levin@unco.edu\\
\and
Tyler Markkanen\\
\small Department of Mathematics, Physics, and Computer Science\\[-0.8ex]
\small Springfield College\\[-0.8ex]
\small 263 Alden Street, Springfield, MA 01109, USA\\
\small\tt tmarkkanen@springfieldcollege.edu
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Mar 9, 2015}{Sep 10, 2015}{Sep 20, 2015}\\
\small Mathematics Subject Classifications: 05C69, 05C63, 05C85, 03D80}



\begin{document}

\maketitle



\begin{abstract}
We investigate the apparent difficulty of finding domatic partitions in graphs using tools from computability theory.  We consider nicely presented (i.e., computable) infinite graphs and show that even if the domatic number is known, there might not be any algorithm for producing a domatic partition of optimal size.  However, we prove that smaller domatic partitions can be constructed if we restrict to \textit{regular} graphs.  Additionally, we establish similar results for total domatic partitions.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} domatic partitions; graph algorithms; infinite regular graphs; computability theory
\end{abstract}




\section{Introduction}
A set $D$ of vertices in a graph $G$ is called {\em dominating} if every vertex of $G$ not in $D$ is adjacent to a vertex in $D$.  A partition of the vertices into $n$ dominating sets is called a {\em domatic $n$-partition}, and the largest such $n$ is called the {\em domatic number} of the graph.  Not surprisingly, finding the domatic number of a graph is non-tractable---deciding whether a graph has domatic number $3$ is $\NP$-complete \cite{gareyjohnson}.  Thus actually producing a domatic partition of optimal size is computationally hard.  The goal of this paper is to better understand domatic partitions by investigating {\em why} domatic partitions are so difficult to produce.  

The complexity of the domatic number and related problems have been widely studied. 
For example, Riege and Rothe proved that the exact versions of the domatic number problem are complete for levels of the boolean hierarchy over $\NP$ \cite{riege}.  Approximations to the domatic number have been studied: it is possible to find domatic partitions of non-optimal size (determined by the size and minimal degree of the graph) in polynomial time \cite{feige}.  Another approach is to restrict to specific classes of graphs.  The domatic number problem remains $\NP$-complete even when restricting to special classes of graphs such as chordal or bipartite \cite{kaplan}.  However, there is a polynomial time algorithm to find the domatic number and the desired partition of a given interval graph \cite{bertossi}.  For more classical results, see \cite{fundom}.


In this paper, we consider infinite graphs, and ask whether it is possible to find domatic partitions of various sizes.  To do this, the graphs will need to be nicely presented; our approach will be to use tools from computability theory.  By ``nicely presented'' graphs we will mean {\em computable} graphs and we will ask whether there exists a {\em computable} domatic partition.  The relevant definitions and background in computability theory will be given in Section \ref{sect-Prelims}, but essentially {\em computable} means ``there is an algorithm which gives\ldots''  For more of a complete background on computability theory, please see \cite{soare} or \cite{rogers}.  Since the finite version of this question is $\NP$-hard, it is not surprising that, in general, computable graphs with domatic number $n \ge 3$ might not even have a computable domatic $3$-partition (every such graph does have a computable domatic 2-partition---these results can be found in \cite{jlm}).  The general case though allows for graphs in which we might not know how many neighbors a particular vertex has.  In this investigation we will thus restrict our focus to {\em regular} graphs (graphs in which every vertex has the same degree).  
This restriction would appear to make it {\em easier} to find domatic partitions---not just because we are restricting the class of graphs we consider, but also because, in attempting to build a domatic partition, we have fewer places where we can make a mistake.  However, we will show in Theorem \ref{thm-nNotn} that there are computable regular graphs with domatic number $n$ but no computable domatic $n$-partition.


Computability theory has proved useful in understanding the complexity of a large number of other graph invariants.  A set of vertices is \emph{independent} if no vertices in the set are adjacent, and an \emph{independent $n$-partition} (or proper vertex coloring) is a partition of the vertices into $n$ independent sets.  The \emph{smallest} $n$ for which there is an independent $n$-partition is the \emph{chromatic number} of the graph.  For finite graphs, deciding the chromatic number is $\NP$-complete, and producing an independent partition of optimal size is computationally difficult.  Bean \cite{bean} established that there are computable graphs with chromatic number as small as $2$ which contain no computable proper vertex coloring of any finite size.  However, if one requires that the degree of each vertex is also computable, then it is possible to find computable independent partition, albeit not of optimal size (the computable chromatic number can be as much as one less than twice the classical chromatic number), a result of Schmerl \cite{schmerl}.  Both of these results pertain directly to infinite graphs, but still tell us something about why coloring graphs in general is difficult.  The first result (and in particular its proof) shows that, in a strong sense, we must consider the entire graph before being confident that we have not made a mistake.  The mistakes we might make can be arbitrarily bad, requiring us to use more and more colors.  However, knowing how many neighbors a vertex has is indeed useful information, even if it is not enough to give an independent partition of smallest possible size.

Mirroring the research for chromatic number, we ask whether there might be computable domatic partitions of size {\em smaller} than the domatic number (but larger than the trivial 2-partition).  In Theorem \ref{n_squared} we give a procedure for producing a (computable) domatic $n$-partition in any computable $k$-regular graph with domatic number $k+1 \ge n^2$.  Whether this gap is the best-possible is not known.  Indeed, for $n \le 4$ we can do slightly better. 

We will begin in Section \ref{sect-Prelims} by recalling some graph-theoretic definitions and introducing the relevant concepts from computability theory.  Then in Section \ref{sect-nNotn}, we will prove that it is not always possible to compute a domatic $n$-partition in computable regular graphs with domatic number $n$.  We will also give an analogous result for {\em total} domatic partitions, a concept that is defined in that section.  We will then turn to the question of whether it is easier to compute {\em smaller} domatic partitions for these graphs.  In Section \ref{sect-Smaller} we show how to compute sub-optimal domatic partitions, and consider what these might look like.  In particular, we will prove that they are not {\em divisible}, that is, they are not the result of taking the union of the sets in a full domatic partition.  In Section \ref{sec-Questions} we conclude with some ideas for future research.

\section{Preliminaries}\label{sect-Prelims}

Recall the following definitions from graph theory.  A set of vertices $D$ in a graph $G$ is {\em dominating}, if each vertex of $G$ not in $D$ is adjacent to a vertex from $D$.  It is always possible to partition the vertices of $G$ into (disjoint) dominating sets and such a partition is called {\em domatic}.  Since we will consider issues of computability, we give an equivalent definition.  A {\em domatic $n$-partition} of a graph $G = (V, E)$ is a function $f : V \to \{1,2,\ldots,n\}$, such that each $D_i = \{v \in V \st f(v) = i\}$ (with $1 \le i \le n$) is a dominating set in $G$, and the collection of these $D_i$ partitions $V$.  The largest $n$ for which $G$ admits a domatic $n$-partition is called the {\em domatic number of $G$}, denoted $d(G)$.  As is tradition, we will usually say that $f$ assigns ``colors'' to vertices.  If a vertex $v$ is either in $D_i$ or adjacent to a vertex in $D_i$, we will say that $v$ is {\em dominated} by color $i$. 

When there exists a domatic $n$-partition, we wish to know if it is a computable function.  Formally, a function $\varphi : \N \to \N$ is {\em computable} if there is some Turing machine, which on input $n$, outputs $\varphi(n)$.  By the Church-Turing thesis, this is equivalent to the existence of an informal algorithm which outputs $\varphi(n)$ on input $n$, and this is the notion of computability that we will generally adopt.  Indeed, we identify $\varphi$ with its algorithm.  Notice that our computable functions have no time or space restrictions, except that both must be finite for each individual input.  Of course, there are algorithms that do not halt on some inputs.  Thus in general we consider {\em partial computable functions}.  We still write $\varphi : \N \to \N$, although the domain need not be all of the natural numbers, and for those numbers $n$ in the domain, we write $\varphi(n)\halts$ and say that $\varphi$ {\em halts} or {\em converges} on $n$.  Otherwise we write $\varphi(n)\nhalts$ and say that $\varphi$ {\em diverges} on $n$.  If a partial computable function converges on all natural numbers, we say it is {\em total computable} or simply {\em computable}. 

The advantage of considering partial computable functions is that we can effectively list all of them: $\{\varphi_0, \varphi_1, \ldots \}$ (there is a universal Turing machine, or alternatively, think of enumerating all of the countably many algorithms in some fixed programming language).  The existence of this effective list of all partial computable functions will allow us to prove that a particular graph does not contain a computable domatic $k$-partition, by showing that $\varphi_e$ is not a domatic $k$-partition for any $e \in \N$---either because $\varphi_e(n)\nhalts$ for some $n$, or because $\varphi_e(n)\halts$ but is ``wrong.''  That is, some vertex is not dominated because of the value of $\varphi_e(n)$.  This process is usually called {\em diagonalizing} against all computable functions, as each partial computable function need only fail on one input (much as happens in Cantor's diagonalization proof that the real numbers are uncountable).

Intuitively, a graph should be computable if there is an algorithm which tells us when two vertices are adjacent.  A little more formally, we take $V = \N$ (although often still refer to vertices as $v_0, v_1, \ldots$) and require that $E \subseteq V \times V$ is computable as a set (we say a set is \emph{computable}, or \emph{decidable}, provided its characteristic function is computable).


Note that while this is a natural definition for a graph being computable, many basic properties of a computable graph might not be computable.  In particular, there need not be an effective procedure for finding all the neighbors of a given vertex; we might have no way to know when to stop looking for another adjacent vertex.  However, all our graphs will be regular, and for these graphs it is possible to compute all the neighbors of a given vertex. To find the neighbors of $v$ in a $k$-regular graph, we simply ask whether $(v, v_i) \in E$ for each $i \in \N$, one at a time, in order.\footnote{All our graphs are undirected, but we still use parentheses to indicate edges for readability.}  Since the graph is computable, we will get an answer for each $i$.  Eventually, we will get a {\em positive} answer $k$ times, and at this point we stop and have our list of $k$ neighbors.  Regularity is just one way we might happen to have a procedure for finding all neighbors---in general, graphs in which finding the degree of vertices is also computable are called {\em highly computable}.


In the next section we will build computable graphs in stages, and we will refer to these as constructions.  At each stage we will add some vertices to the graph.  As soon as we do this, we must say exactly to which of the previously mentioned vertices the new vertices are adjacent.  As long as we do this at each stage, the resulting graph will be computable---the algorithm for deciding whether $(v_i, v_j) \in E$ is simply to run through the construction of our graph until a stage at which both $v_i$ and $v_j$ are mentioned, and check whether we said they were adjacent by that stage.  

While building the graph, we will also be waiting for each $\varphi_e$ to converge on some fixed finite set of vertices so that we can ensure $\varphi_e$ is not a domatic partition.  If $\varphi_e$ never converges, we ``win'' for free (in the sense that $\varphi_e$ can never be a domatic partition of the graph).  If $\varphi_e$ does converge, then we build the next part of the graph in a way to ``defeat'' $\varphi_e$.  But because the graph must be computable, we cannot add any new edges between vertices that were put into the graph previously.  We could add a new vertex adjacent to one previously mentioned, except we might run into issues with the regularity requirement.  If the plan was to wait for $\varphi_e$ to converge on $v_i$, and then add a vertex adjacent to $v_i$, we run the risk that $\varphi_e$ will appear never to converge on $v_i$ at all.  In that case we would need to enumerate all the neighbors of $v_i$ by some finite stage.  After that stage, we might discover that we were wrong, that is, $\varphi_e(v_i)\halts$, and we now cannot put any more vertices adjacent to $v_i$ without breaking regularity.  For this reason, our constructions will only add vertices adjacent to other recently-enumerated vertices.  In particular, the methods we use to diagonalize against all $\varphi_e$ must account for the fact that a proposed domatic partition on some small subset of vertices can influence how vertices that are arbitrarily far away must be partitioned.



\section{Computable Domatic Number}\label{sect-nNotn}

Define the {\em computable domatic number} $d^c(G)$ to be the largest $n$ for which there is a computable domatic $n$-partition of $G$ (i.e., the domatic $n$-partition is a computable function).  Given a computable graph $G$, there is no reason to think that $d(G) = d^c(G)$. Indeed, in general, there are computable graphs with $d(G) = n$ but $d^c(G) = 2$ for each $n \ge 3$, as shown in \cite{jlm}.  These graphs are not regular, however.  We begin by showing that even for regular graphs, we might have $d(G) > d^c(G)$.


\begin{theorem}\label{thm-nNotn}
For each $n \ge 3$, there is an $(n-1)$-regular graph $G$ with $d(G) = n$ and $d^c(G) = n-1$.
\end{theorem}

The construction used in \cite{jlm} prevented $\varphi_e$ from being a domatic partition by adding a new vertex adjacent to a large set of vertices that $\varphi_e$ partitioned identically.  This technique has no hope of working here where we cannot change the degree of vertices.  Instead, our proof will rely on our ability to generate a {\em chain} of vertices in which we can guarantee that certain vertices must be colored identically. 


\begin{definition}
A {\em $K_n^-$-link} is the graph on vertices $\{l,r, v_1, \ldots, v_{n-2}\}$ with edges connecting all pairs of vertices except $l$ and $r$  (in other-words, we have $K_n - (l,r)$).  We call $l$ a {\em left-outer vertex}, $r$ a {\em right-outer vertex}, and the vertices $\{v_1, \ldots, v_{n-2}\}$ all {\em inner vertices}.  A {\em $K_n^-$-chain} consists of a sequence of $K_n^-$-links in which each right-outer vertex of one link is adjacent to the left-outer vertex of the next link.  The number of links in a chain is its {\em length}.  For example, see Figure \ref{fig-k6chain}.
\end{definition}


\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=.8cm,y=.8cm]
\draw (2,3)-- (1,3);
\draw (1,3)-- (0.5,2.13);
\draw (0.5,2.13)-- (1,1.27);
\draw (1,1.27)-- (2,1.27);
\draw (2,1.27)-- (2.5,2.13);
\draw (2.5,2.13)-- (2,3);
\draw (1,3)-- (2,1.27);
\draw (1,3)-- (1,1.27);
\draw (2,3)-- (1,1.27);
\draw (2,3)-- (2,1.27);
\draw (0.5,2.13)-- (2,3);
\draw (0.5,2.13)-- (2,1.27);
\draw (2.5,2.13)-- (1,3);
\draw (2.5,2.13)-- (1,1.27);
\draw (5,3)-- (4,3);
\draw (4,3)-- (3.5,2.13);
\draw (3.5,2.13)-- (4,1.27);
\draw (4,1.27)-- (5,1.27);
\draw (5,1.27)-- (5.5,2.13);
\draw (5.5,2.13)-- (5,3);
\draw (4,3)-- (5,1.27);
\draw (4,3)-- (4,1.27);
\draw (5,3)-- (4,1.27);
\draw (5,3)-- (5,1.27);
\draw (3.5,2.13)-- (5,3);
\draw (3.5,2.13)-- (5,1.27);
\draw (5.5,2.13)-- (4,3);
\draw (5.5,2.13)-- (4,1.27);
\draw (8,3)-- (7,3);
\draw (7,3)-- (6.5,2.13);
\draw (6.5,2.13)-- (7,1.27);
\draw (7,1.27)-- (8,1.27);
\draw (8,1.27)-- (8.5,2.13);
\draw (8.5,2.13)-- (8,3);
\draw (7,3)-- (8,1.27);
\draw (7,3)-- (7,1.27);
\draw (8,3)-- (7,1.27);
\draw (8,3)-- (8,1.27);
\draw (6.5,2.13)-- (8,3);
\draw (6.5,2.13)-- (8,1.27);
\draw (8.5,2.13)-- (7,3);
\draw (8.5,2.13)-- (7,1.27);
\draw (11,3)-- (10,3);
\draw (10,3)-- (9.5,2.13);
\draw (9.5,2.13)-- (10,1.27);
\draw (10,1.27)-- (11,1.27);
\draw (11,1.27)-- (11.5,2.13);
\draw (11.5,2.13)-- (11,3);
\draw (10,3)-- (11,1.27);
\draw (10,3)-- (10,1.27);
\draw (11,3)-- (10,1.27);
\draw (11,3)-- (11,1.27);
\draw (9.5,2.13)-- (11,3);
\draw (9.5,2.13)-- (11,1.27);
\draw (11.5,2.13)-- (10,3);
\draw (11.5,2.13)-- (10,1.27);
\draw (2.5,2.13)-- (3.5,2.13);
\draw (5.5,2.13)-- (6.5,2.13);
\draw (8.5,2.13)-- (9.5,2.13);
\begin{scriptsize}
\fill [color=black] (2,3) circle (1.5pt);
\draw[color=black] (2,3) node[above] {$v_2$};
\fill [color=black] (1,3) circle (1.5pt);
\draw[color=black] (1,3) node[above] {$v_1$};
\fill [color=black] (0.5,2.13) circle (1.5pt);
\draw[color=black] (0.5,2.13) node[below left] {$l$};
\fill [color=black] (1,1.27) circle (1.5pt);
\draw[color=black] (1,1.27) node[below] {$v_4$};
\fill [color=black] (2,1.27) circle (1.5pt);
\draw[color=black] (2,1.27) node[below] {$v_3$};
\fill [color=black] (2.5,2.13) circle (1.5pt);
\draw[color=black] (2.5,2.13) node[below right] {$r$};
\fill [color=black] (5,3) circle (1.5pt);
\fill [color=black] (4,3) circle (1.5pt);
\fill [color=black] (3.5,2.13) circle (1.5pt);
\draw[color=black] (3.5,2.13) node[below left] {$l$};
\fill [color=black] (4,1.27) circle (1.5pt);
\fill [color=black] (5,1.27) circle (1.5pt);
\fill [color=black] (5.5,2.13) circle (1.5pt);
\fill [color=black] (8,3) circle (1.5pt);
\fill [color=black] (7,3) circle (1.5pt);
\fill [color=black] (6.5,2.13) circle (1.5pt);
\fill [color=black] (7,1.27) circle (1.5pt);
\fill [color=black] (8,1.27) circle (1.5pt);
\fill [color=black] (8.5,2.13) circle (1.5pt);
\fill [color=black] (11,3) circle (1.5pt);
\fill [color=black] (10,3) circle (1.5pt);
\fill [color=black] (9.5,2.13) circle (1.5pt);
\fill [color=black] (10,1.27) circle (1.5pt);
\fill [color=black] (11,1.27) circle (1.5pt);
\fill [color=black] (11.5,2.13) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}
\caption{A $K_6^-$-chain of length 4.}\label{fig-k6chain}
\end{center}
\end{figure}

\begin{lemma}\label{chainLemma}
Suppose a graph with domatic number $n$ contains a $K_n^-$-chain.  Then in any domatic $n$-partition, all left-outer vertices in the same chain must be colored identically to each other and distinctly from all the right-outer vertices in the same chain, which themselves must also be colored identically.
\end{lemma}

\begin{proof}
Notice first, each vertex in the chain has degree $n-1$ (we assume that either the first left-outer vertex and last right-outer vertex are each adjacent to exactly one vertex outside the chain or else that the chain is infinite).  Thus in any domatic $n$-partition, no vertex can be adjacent to two vertices of the same color, and as such each link must contain exactly one vertex of each color.  In the first link, say the left-outer vertex is colored red, and the right-outer vertex is colored blue.  None of the inner vertices can be colored red or blue, so within the first link, the right-outer vertex is dominated by every color except red.  Thus the left-outer vertex of the next link must be red again.  Now this vertex is already dominated by red and blue, so the inner vertices of the second link must be the other $n-2$ colors.  Each of the inner vertices will be dominated by all colors except blue, forcing the right-outer vertex of the second link to be blue again.  We can inductively extend this argument to the entire chain.
\end{proof}


We are now ready to prove Theorem \ref{thm-nNotn}.

\begin{proof}[Proof of Theorem \ref{thm-nNotn}]
We build the desired $(n-1)$-regular graph $G$ and a computable domatic $(n-1)$-partition of $G$, while at the same time diagonalizing against all partial computable functions $\varphi_e$, which we interpret as candidates for a computable domatic $n$-partition of $G$.  The graph will be built in stages; at each stage $s$ we will have a finite graph $G_s$ consisting of some number of $K_n^-$-chains.  In fact, $G_s$ will be $\bigcup_{e\le s} T_{e,s}$, where each $T_{e,s}$ is either one or two finite $K_n^-$-chains which we have built for the purpose of ensuring that $\varphi_e$ is not a domatic $n$-partition.  Each stage of the construction will consist of increasing the length of each $T_{e,s}$, adding a new $T_{e,s}$, and possibly connecting the two $K_n^-$-chains in a particular $T_{e,s}$ to form one longer $K_n^-$-chain.  Our final graph will be $G = \bigcup_{s\in\N}G_s = \bigcup_{e}T_{e}$, consisting of infinitely many $K_n^-$-chains each of infinite length (where each $T_e = \bigcup_{s\ge e}T_{e,s}$ is either one or two infinitely long $K_n^-$-chains).

In order to diagonalize against each $\varphi_e$, we will focus on four vertices in each $T_{e,s}$.  When first initialized as $T_{e,e}$, this graph will consist of two disjoint $K_n^-$-chains each of length 1 (that is a single $K_n^-$-link).  Call the left-outer vertices of these two links $l_e^1$ and $l_e^2$, and the right-outer vertices of these two links $r_e^1$ and $r_e^2$, respectively.

\textit{Construction:}  At stage $0$, initialize $G_0 = T_{0,0}$ as two disjoint $K_n^-$-chains each of length 1, and then move on to stage $1$.  At any stage $s \ge 1$, assume that we have already defined $G_{s-1} = \bigcup_{e < s} T_{e, s-1}$, where each $T_{e,s-1}$ is either one or two $K_n^-$-chains (of some finite length).  Proceed as follows:
\begin{enumerate}
\item Initialize $T_{s, s}$ as two disjoint $K_n^-$-chains each of length 1.
\item For each $e < s$ for which $T_{e,s-1}$ consists of two chains, run $\varphi_e$ on the vertices $\{l_e^1,  l_e^2,  r_e^1,  r_e^2\}$.  Do nothing, unless $\varphi_e$ halts on all four of these inputs, in which case:
	\begin{enumerate}
	\item If $\varphi_e(l_e^1) = \varphi_e(l_e^2)$, add a single link to connect the two chains of $T_{e, s-1}$, connecting the right ends of both chains, as in Figure \ref{fig-righttoright}.
	\item If $\varphi_e(l_e^1) \ne \varphi_e(l_e^2)$, add a single link to connect the two chains of $T_{e, s-1}$, connecting the right end of one chain to the left end of the other, as in Figure \ref{fig-righttoleft}. 
	\end{enumerate}
\item For each $e < s$, form $T_{e,s}$ by adding a single link to each end of all (one or two) of the $K_n^-$-chains in $T_{e,s-1}$.  Move on to stage $s+1$.
\end{enumerate}
This completes the construction.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\draw (1.5,3)-- (1,3);
\draw (1,3)-- (0.75,2.57);
\draw (0.75,2.57)-- (1,2.13);
\draw (1,2.13)-- (1.5,2.13);
\draw (1.5,2.13)-- (1.75,2.57);
\draw (1.75,2.57)-- (1.5,3);
\draw (1,3)-- (1.5,2.13);
\draw (1,3)-- (1,2.13);
\draw (1.5,3)-- (1,2.13);
\draw (1.5,3)-- (1.5,2.13);
\draw (0.75,2.57)-- (1.5,3);
\draw (0.75,2.57)-- (1.5,2.13);
\draw (1.75,2.57)-- (1,3);
\draw (1.75,2.57)-- (1,2.13);
\draw (3,3)-- (2.5,3);
\draw (2.5,3)-- (2.25,2.57);
\draw (2.25,2.57)-- (2.5,2.13);
\draw (2.5,2.13)-- (3,2.13);
\draw (3,2.13)-- (3.25,2.57);
\draw (3.25,2.57)-- (3,3);
\draw (2.5,3)-- (3,2.13);
\draw (2.5,3)-- (2.5,2.13);
\draw (3,3)-- (2.5,2.13);
\draw (3,3)-- (3,2.13);
\draw (2.25,2.57)-- (3,3);
\draw (2.25,2.57)-- (3,2.13);
\draw (3.25,2.57)-- (2.5,3);
\draw (3.25,2.57)-- (2.5,2.13);
\draw (4.5,3)-- (4,3);
\draw (4,3)-- (3.75,2.57);
\draw (3.75,2.57)-- (4,2.13);
\draw (4,2.13)-- (4.5,2.13);
\draw (4.5,2.13)-- (4.75,2.57);
\draw (4.75,2.57)-- (4.5,3);
\draw (4,3)-- (4.5,2.13);
\draw (4,3)-- (4,2.13);
\draw (4.5,3)-- (4,2.13);
\draw (4.5,3)-- (4.5,2.13);
\draw (3.75,2.57)-- (4.5,3);
\draw (3.75,2.57)-- (4.5,2.13);
\draw (4.75,2.57)-- (4,3);
\draw (4.75,2.57)-- (4,2.13);
\draw (6,3)-- (5.5,3);
\draw (5.5,3)-- (5.25,2.57);
\draw (5.25,2.57)-- (5.5,2.13);
\draw (5.5,2.13)-- (6,2.13);
\draw (6,2.13)-- (6.25,2.57);
\draw (6.25,2.57)-- (6,3);
\draw (5.5,3)-- (6,2.13);
\draw (5.5,3)-- (5.5,2.13);
\draw (6,3)-- (5.5,2.13);
\draw (6,3)-- (6,2.13);
\draw (5.25,2.57)-- (6,3);
\draw (5.25,2.57)-- (6,2.13);
\draw (6.25,2.57)-- (5.5,3);
\draw (6.25,2.57)-- (5.5,2.13);
\draw (1.75,2.57)-- (2.25,2.57);
\draw (3.25,2.57)-- (3.75,2.57);
\draw (4.75,2.57)-- (5.25,2.57);
\draw (7.5,3)-- (7,3);
\draw (7,3)-- (6.75,2.57);
\draw (6.75,2.57)-- (7,2.13);
\draw (7,2.13)-- (7.5,2.13);
\draw (7.5,2.13)-- (7.75,2.57);
\draw (7.75,2.57)-- (7.5,3);
\draw (7,3)-- (7.5,2.13);
\draw (7,3)-- (7,2.13);
\draw (7.5,3)-- (7,2.13);
\draw (7.5,3)-- (7.5,2.13);
\draw (6.75,2.57)-- (7.5,3);
\draw (6.75,2.57)-- (7.5,2.13);
\draw (7.75,2.57)-- (7,3);
\draw (7.75,2.57)-- (7,2.13);
\draw (6.75,2.57)-- (6.25,2.57);
\draw [dash pattern=on 2pt off 2pt] (0.75,2.57)-- (0,2.57);
\draw (8,1.3)-- (8,0.7);
\draw (8,0.7)-- (8.52,0.4);
\draw (8.52,0.4)-- (9.04,0.7);
\draw (9.04,0.7)-- (9.04,1.3);
\draw (9.04,1.3)-- (8.52,1.6);
\draw (8.52,1.6)-- (8,1.3);
\draw (8,0.7)-- (9.04,1.3);
\draw (8,0.7)-- (9.04,0.7);
\draw (8,1.3)-- (9.04,0.7);
\draw (8,1.3)-- (9.04,1.3);
\draw (8.52,0.4)-- (8,1.3);
\draw (8.52,0.4)-- (9.04,1.3);
\draw (8.52,1.6)-- (8,0.7);
\draw (8.52,1.6)-- (9.04,0.7);
\draw (7.75,2.57)-- (8.52,1.6);
\draw (1,-1)-- (1.5,-0.13);
\draw (1,-1)-- (1,-0.13);
\draw (1.5,-1)-- (1,-0.13);
\draw (1.5,-1)-- (1.5,-0.13);
\draw (0.75,-0.57)-- (1.5,-1);
\draw (0.75,-0.57)-- (1.5,-0.13);
\draw (1.75,-0.57)-- (1,-1);
\draw (1.75,-0.57)-- (1,-0.13);
\draw (2.5,-1)-- (3,-0.13);
\draw (2.5,-1)-- (2.5,-0.13);
\draw (3,-1)-- (2.5,-0.13);
\draw (3,-1)-- (3,-0.13);
\draw (2.25,-0.57)-- (3,-1);
\draw (2.25,-0.57)-- (3,-0.13);
\draw (3.25,-0.57)-- (2.5,-1);
\draw (3.25,-0.57)-- (2.5,-0.13);
\draw (4,-1)-- (4.5,-0.13);
\draw (4,-1)-- (4,-0.13);
\draw (4.5,-1)-- (4,-0.13);
\draw (4.5,-1)-- (4.5,-0.13);
\draw (3.75,-0.57)-- (4.5,-1);
\draw (3.75,-0.57)-- (4.5,-0.13);
\draw (4.75,-0.57)-- (4,-1);
\draw (4.75,-0.57)-- (4,-0.13);
\draw (5.5,-1)-- (6,-0.13);
\draw (5.5,-1)-- (5.5,-0.13);
\draw (6,-1)-- (5.5,-0.13);
\draw (6,-1)-- (6,-0.13);
\draw (5.25,-0.57)-- (6,-1);
\draw (5.25,-0.57)-- (6,-0.13);
\draw (6.25,-0.57)-- (5.5,-1);
\draw (6.25,-0.57)-- (5.5,-0.13);
\draw (1.75,-0.57)-- (2.25,-0.57);
\draw (3.25,-0.57)-- (3.75,-0.57);
\draw (4.75,-0.57)-- (5.25,-0.57);
\draw (7,-1)-- (7.5,-0.13);
\draw (7,-1)-- (7,-0.13);
\draw (7.5,-1)-- (7,-0.13);
\draw (7.5,-1)-- (7.5,-0.13);
\draw (6.75,-0.57)-- (7.5,-1);
\draw (6.75,-0.57)-- (7.5,-0.13);
\draw (7.75,-0.57)-- (7,-1);
\draw (7.75,-0.57)-- (7,-0.13);
\draw (6.75,-0.57)-- (6.25,-0.57);
\draw [dash pattern=on 2pt off 2pt] (0.75,-0.57)-- (0,-0.57);
\draw (7.75,-0.57)-- (8.52,0.4);
\draw (1,-0.13)-- (1.5,-0.13);
\draw (1.5,-0.13)-- (1.75,-0.57);
\draw (1.75,-0.57)-- (1.5,-1);
\draw (1.5,-1)-- (1,-1);
\draw (1,-1)-- (0.75,-0.57);
\draw (0.75,-0.57)-- (1,-0.13);
\draw (2.5,-0.13)-- (3,-0.13);
\draw (3,-0.13)-- (3.25,-0.57);
\draw (3.25,-0.57)-- (3,-1);
\draw (3,-1)-- (2.5,-1);
\draw (2.5,-1)-- (2.25,-0.57);
\draw (2.25,-0.57)-- (2.5,-0.13);
\draw (4,-0.13)-- (4.5,-0.13);
\draw (4.5,-0.13)-- (4.75,-0.57);
\draw (4.75,-0.57)-- (4.5,-1);
\draw (4.5,-1)-- (4,-1);
\draw (4,-1)-- (3.75,-0.57);
\draw (3.75,-0.57)-- (4,-0.13);
\draw (5.5,-0.13)-- (6,-0.13);
\draw (6,-0.13)-- (6.25,-0.57);
\draw (6.25,-0.57)-- (6,-1);
\draw (6,-1)-- (5.5,-1);
\draw (5.5,-1)-- (5.25,-0.57);
\draw (5.25,-0.57)-- (5.5,-0.13);
\draw (6.75,-0.57)-- (7,-0.13);
\draw (7,-0.13)-- (7.5,-0.13);
\draw (7.5,-0.13)-- (7.75,-0.57);
\draw (7.75,-0.57)-- (7.5,-1);
\draw (7.5,-1)-- (7,-1);
\draw (7,-1)-- (6.75,-0.57);
\begin{scriptsize}
\fill [color=black] (1.5,3) circle (1.0pt);
\fill [color=black] (1,3) circle (1.0pt);
\fill [color=black] (0.75,2.57) circle (1.0pt);
\fill [color=black] (1,2.13) circle (1.0pt);
\fill [color=black] (1.5,2.13) circle (1.0pt);
\fill [color=black] (1.75,2.57) circle (1.0pt);
\fill [color=black] (3,3) circle (1.0pt);
\fill [color=black] (2.5,3) circle (1.0pt);
\fill [color=black] (2.25,2.57) circle (1.0pt);
\fill [color=black] (2.5,2.13) circle (1.0pt);
\fill [color=black] (3,2.13) circle (1.0pt);
\fill [color=black] (3.25,2.57) circle (1.0pt);
\fill [color=black] (4.5,3) circle (1.0pt);
\fill [color=black] (4,3) circle (1.0pt);
\fill [color=black] (3.75,2.57) circle (1.5pt);
\draw (3.7, 2.57) node[below]{$l_e^1$};
\fill [color=black] (4,2.13) circle (1.0pt);
\fill [color=black] (4.5,2.13) circle (1.0pt);
\fill [color=black] (4.75,2.57) circle (1.0pt);
\draw (4.6, 2.57) node[below right]{$r_e^1$};
\fill [color=black] (6,3) circle (1.0pt);
\fill [color=black] (5.5,3) circle (1.0pt);
\fill [color=black] (5.25,2.57) circle (1.0pt);
\fill [color=black] (5.5,2.13) circle (1.0pt);
\fill [color=black] (6,2.13) circle (1.0pt);
\fill [color=black] (6.25,2.57) circle (1.0pt);
\fill [color=black] (7.5,3) circle (1.0pt);
\fill [color=black] (7,3) circle (1.0pt);
\fill [color=black] (6.75,2.57) circle (1.0pt);
\fill [color=black] (7,2.13) circle (1.0pt);
\fill [color=black] (7.5,2.13) circle (1.0pt);
\fill [color=black] (7.75,2.57) circle (1.0pt);
\fill [color=black] (8,1.3) circle (1.5pt);
\fill [color=black] (8,0.7) circle (1.5pt);
\fill [color=black] (8.52,0.4) circle (1.5pt);
\fill [color=black] (9.04,0.7) circle (1.5pt);
\fill [color=black] (9.04,1.3) circle (1.5pt);
\fill [color=black] (8.52,1.6) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.0pt);
\fill [color=black] (1.5,-0.13) circle (1.0pt);
\fill [color=black] (1,-1) circle (1.0pt);
\fill [color=black] (1,-0.13) circle (1.0pt);
\fill [color=black] (1.5,-1) circle (1.0pt);
\fill [color=black] (1,-0.13) circle (1.0pt);
\fill [color=black] (1.5,-1) circle (1.0pt);
\fill [color=black] (1.5,-0.13) circle (1.0pt);
\fill [color=black] (0.75,-0.57) circle (1.0pt);
\fill [color=black] (1.5,-1) circle (1.0pt);
\fill [color=black] (0.75,-0.57) circle (1.0pt);
\fill [color=black] (1.5,-0.13) circle (1.0pt);
\fill [color=black] (1.75,-0.57) circle (1.0pt);
\fill [color=black] (1,-1) circle (1.0pt);
\fill [color=black] (1.75,-0.57) circle (1.0pt);
\fill [color=black] (1,-0.13) circle (1.0pt);
\fill [color=black] (2.5,-1) circle (1.0pt);
\fill [color=black] (3,-0.13) circle (1.0pt);
\fill [color=black] (2.5,-1) circle (1.0pt);
\fill [color=black] (2.5,-0.13) circle (1.0pt);
\fill [color=black] (3,-1) circle (1.0pt);
\fill [color=black] (2.5,-0.13) circle (1.0pt);
\fill [color=black] (3,-1) circle (1.0pt);
\fill [color=black] (3,-0.13) circle (1.0pt);
\fill [color=black] (2.25,-0.57) circle (1.0pt);
\fill [color=black] (3,-1) circle (1.0pt);
\fill [color=black] (2.25,-0.57) circle (1.0pt);
\fill [color=black] (3,-0.13) circle (1.0pt);
\fill [color=black] (3.25,-0.57) circle (1.0pt);
\fill [color=black] (2.5,-1) circle (1.0pt);
\fill [color=black] (3.25,-0.57) circle (1.0pt);
\fill [color=black] (2.5,-0.13) circle (1.0pt);
\fill [color=black] (4,-1) circle (1.0pt);
\fill [color=black] (4.5,-0.13) circle (1.0pt);
\fill [color=black] (4,-1) circle (1.0pt);
\fill [color=black] (4,-0.13) circle (1.0pt);
\fill [color=black] (4.5,-1) circle (1.0pt);
\fill [color=black] (4,-0.13) circle (1.0pt);
\fill [color=black] (4.5,-1) circle (1.0pt);
\fill [color=black] (4.5,-0.13) circle (1.0pt);
\fill [color=black] (3.75,-0.57) circle (1.0pt);
\fill [color=black] (4.5,-1) circle (1.0pt);
\fill [color=black] (3.75,-0.57) circle (1.0pt);
\fill [color=black] (4.5,-0.13) circle (1.0pt);
\fill [color=black] (4.75,-0.57) circle (1.0pt);
\fill [color=black] (4,-1) circle (1.0pt);
\fill [color=black] (4.75,-0.57) circle (1.0pt);
\fill [color=black] (4,-0.13) circle (1.0pt);
\fill [color=black] (5.5,-1) circle (1.0pt);
\fill [color=black] (6,-0.13) circle (1.0pt);
\fill [color=black] (5.5,-1) circle (1.0pt);
\fill [color=black] (5.5,-0.13) circle (1.0pt);
\fill [color=black] (6,-1) circle (1.0pt);
\fill [color=black] (5.5,-0.13) circle (1.0pt);
\fill [color=black] (6,-1) circle (1.0pt);
\fill [color=black] (6,-0.13) circle (1.0pt);
\fill [color=black] (5.25,-0.57) circle (1.0pt);
\fill [color=black] (6,-1) circle (1.0pt);
\fill [color=black] (5.25,-0.57) circle (1.0pt);
\fill [color=black] (6,-0.13) circle (1.0pt);
\fill [color=black] (6.25,-0.57) circle (1.0pt);
\fill [color=black] (5.5,-1) circle (1.0pt);
\fill [color=black] (6.25,-0.57) circle (1.0pt);
\fill [color=black] (5.5,-0.13) circle (1.0pt);
\fill [color=black] (1.75,-0.57) circle (1.0pt);
\fill [color=black] (2.25,-0.57) circle (1.0pt);
\fill [color=black] (3.25,-0.57) circle (1.0pt);
\fill [color=black] (3.75,-0.57) circle (1.5pt);
\draw (3.7, -0.57) node[below]{$l_e^2$};
\fill [color=black] (4.75,-0.57) circle (1.0pt);
\draw (4.6, -0.57) node[below right]{$r_e^2$};
\fill [color=black] (5.25,-0.57) circle (1.0pt);
\fill [color=black] (7,-1) circle (1.0pt);
\fill [color=black] (7.5,-0.13) circle (1.0pt);
\fill [color=black] (7,-1) circle (1.0pt);
\fill [color=black] (7,-0.13) circle (1.0pt);
\fill [color=black] (7.5,-1) circle (1.0pt);
\fill [color=black] (7,-0.13) circle (1.0pt);
\fill [color=black] (7.5,-1) circle (1.0pt);
\fill [color=black] (7.5,-0.13) circle (1.0pt);
\fill [color=black] (6.75,-0.57) circle (1.0pt);
\fill [color=black] (7.5,-1) circle (1.0pt);
\fill [color=black] (6.75,-0.57) circle (1.0pt);
\fill [color=black] (7.5,-0.13) circle (1.0pt);
\fill [color=black] (7.75,-0.57) circle (1.0pt);
\fill [color=black] (7,-1) circle (1.0pt);
\fill [color=black] (7.75,-0.57) circle (1.0pt);
\fill [color=black] (7,-0.13) circle (1.0pt);
\fill [color=black] (6.75,-0.57) circle (1.0pt);
\fill [color=black] (6.25,-0.57) circle (1.0pt);
\fill [color=black] (0.75,-0.57) circle (1.0pt);
\end{scriptsize}

\end{tikzpicture}
\end{center}
\caption{$T_e$ if $\varphi_e(l_e^1) = \varphi_e(l_e^2)$ after $\varphi_e$ has halted.}\label{fig-righttoright}
\end{figure}


\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\draw (1.5,3)-- (1,3);
\draw (1,3)-- (0.75,2.57);
\draw (0.75,2.57)-- (1,2.13);
\draw (1,2.13)-- (1.5,2.13);
\draw (1.5,2.13)-- (1.75,2.57);
\draw (1.75,2.57)-- (1.5,3);
\draw (1,3)-- (1.5,2.13);
\draw (1,3)-- (1,2.13);
\draw (1.5,3)-- (1,2.13);
\draw (1.5,3)-- (1.5,2.13);
\draw (0.75,2.57)-- (1.5,3);
\draw (0.75,2.57)-- (1.5,2.13);
\draw (1.75,2.57)-- (1,3);
\draw (1.75,2.57)-- (1,2.13);
\draw (3,3)-- (2.5,3);
\draw (2.5,3)-- (2.25,2.57);
\draw (2.25,2.57)-- (2.5,2.13);
\draw (2.5,2.13)-- (3,2.13);
\draw (3,2.13)-- (3.25,2.57);
\draw (3.25,2.57)-- (3,3);
\draw (2.5,3)-- (3,2.13);
\draw (2.5,3)-- (2.5,2.13);
\draw (3,3)-- (2.5,2.13);
\draw (3,3)-- (3,2.13);
\draw (2.25,2.57)-- (3,3);
\draw (2.25,2.57)-- (3,2.13);
\draw (3.25,2.57)-- (2.5,3);
\draw (3.25,2.57)-- (2.5,2.13);
\draw (4.5,3)-- (4,3);
\draw (4,3)-- (3.75,2.57);
\draw (3.75,2.57)-- (4,2.13);
\draw (4,2.13)-- (4.5,2.13);
\draw (4.5,2.13)-- (4.75,2.57);
\draw (4.75,2.57)-- (4.5,3);
\draw (4,3)-- (4.5,2.13);
\draw (4,3)-- (4,2.13);
\draw (4.5,3)-- (4,2.13);
\draw (4.5,3)-- (4.5,2.13);
\draw (3.75,2.57)-- (4.5,3);
\draw (3.75,2.57)-- (4.5,2.13);
\draw (4.75,2.57)-- (4,3);
\draw (4.75,2.57)-- (4,2.13);
\draw (6,3)-- (5.5,3);
\draw (5.5,3)-- (5.25,2.57);
\draw (5.25,2.57)-- (5.5,2.13);
\draw (5.5,2.13)-- (6,2.13);
\draw (6,2.13)-- (6.25,2.57);
\draw (6.25,2.57)-- (6,3);
\draw (5.5,3)-- (6,2.13);
\draw (5.5,3)-- (5.5,2.13);
\draw (6,3)-- (5.5,2.13);
\draw (6,3)-- (6,2.13);
\draw (5.25,2.57)-- (6,3);
\draw (5.25,2.57)-- (6,2.13);
\draw (6.25,2.57)-- (5.5,3);
\draw (6.25,2.57)-- (5.5,2.13);
\draw (1.75,2.57)-- (2.25,2.57);
\draw (3.25,2.57)-- (3.75,2.57);
\draw (4.75,2.57)-- (5.25,2.57);
\draw (7.5,3)-- (7,3);
\draw (7,3)-- (6.75,2.57);
\draw (6.75,2.57)-- (7,2.13);
\draw (7,2.13)-- (7.5,2.13);
\draw (7.5,2.13)-- (7.75,2.57);
\draw (7.75,2.57)-- (7.5,3);
\draw (7,3)-- (7.5,2.13);
\draw (7,3)-- (7,2.13);
\draw (7.5,3)-- (7,2.13);
\draw (7.5,3)-- (7.5,2.13);
\draw (6.75,2.57)-- (7.5,3);
\draw (6.75,2.57)-- (7.5,2.13);
\draw (7.75,2.57)-- (7,3);
\draw (7.75,2.57)-- (7,2.13);
\draw (6.75,2.57)-- (6.25,2.57);
\draw [dash pattern=on 2pt off 2pt] (0.75,2.57)-- (0,2.57);
\draw (4.6,1.61)-- (3.9,1.61);
\draw (3.9,1.61)-- (3.55,1);
\draw (3.55,1)-- (3.9,0.4);
\draw (3.9,0.4)-- (4.6,0.4);
\draw (4.6,0.4)-- (4.95,1);
\draw (4.95,1)-- (4.6,1.61);
\draw (3.9,1.61)-- (4.6,0.4);
\draw (3.9,1.61)-- (3.9,0.4);
\draw (4.6,1.61)-- (3.9,0.4);
\draw (4.6,1.61)-- (4.6,0.4);
\draw (3.55,1)-- (4.6,1.61);
\draw (3.55,1)-- (4.6,0.4);
\draw (4.95,1)-- (3.9,1.61);
\draw (4.95,1)-- (3.9,0.4);
\draw (1,-1)-- (1.5,-0.13);
\draw (1,-1)-- (1,-0.13);
\draw (1.5,-1)-- (1,-0.13);
\draw (1.5,-1)-- (1.5,-0.13);
\draw (0.75,-0.57)-- (1.5,-1);
\draw (0.75,-0.57)-- (1.5,-0.13);
\draw (1.75,-0.57)-- (1,-1);
\draw (1.75,-0.57)-- (1,-0.13);
\draw (2.5,-1)-- (3,-0.13);
\draw (2.5,-1)-- (2.5,-0.13);
\draw (3,-1)-- (2.5,-0.13);
\draw (3,-1)-- (3,-0.13);
\draw (2.25,-0.57)-- (3,-1);
\draw (2.25,-0.57)-- (3,-0.13);
\draw (3.25,-0.57)-- (2.5,-1);
\draw (3.25,-0.57)-- (2.5,-0.13);
\draw (4,-1)-- (4.5,-0.13);
\draw (4,-1)-- (4,-0.13);
\draw (4.5,-1)-- (4,-0.13);
\draw (4.5,-1)-- (4.5,-0.13);
\draw (3.75,-0.57)-- (4.5,-1);
\draw (3.75,-0.57)-- (4.5,-0.13);
\draw (4.75,-0.57)-- (4,-1);
\draw (4.75,-0.57)-- (4,-0.13);
\draw (5.5,-1)-- (6,-0.13);
\draw (5.5,-1)-- (5.5,-0.13);
\draw (6,-1)-- (5.5,-0.13);
\draw (6,-1)-- (6,-0.13);
\draw (5.25,-0.57)-- (6,-1);
\draw (5.25,-0.57)-- (6,-0.13);
\draw (6.25,-0.57)-- (5.5,-1);
\draw (6.25,-0.57)-- (5.5,-0.13);
\draw (1.75,-0.57)-- (2.25,-0.57);
\draw (3.25,-0.57)-- (3.75,-0.57);
\draw (4.75,-0.57)-- (5.25,-0.57);
\draw (7,-1)-- (7.5,-0.13);
\draw (7,-1)-- (7,-0.13);
\draw (7.5,-1)-- (7,-0.13);
\draw (7.5,-1)-- (7.5,-0.13);
\draw (6.75,-0.57)-- (7.5,-1);
\draw (6.75,-0.57)-- (7.5,-0.13);
\draw (7.75,-0.57)-- (7,-1);
\draw (7.75,-0.57)-- (7,-0.13);
\draw (6.75,-0.57)-- (6.25,-0.57);
\draw [dash pattern=on 2pt off 2pt] (7.75,-0.57)-- (8.5,-0.57);
\draw (4.95,1)-- (7.75,1);
\draw (3.55,1)-- (0.75,1);
\draw [shift={(7.75,1.78)}] plot[domain=-1.57:1.57,variable=\t]({1*0.78*cos(\t r)+0*0.78*sin(\t r)},{0*0.78*cos(\t r)+1*0.78*sin(\t r)});
\draw [shift={(0.75,0.22)}] plot[domain=1.57:4.71,variable=\t]({1*0.78*cos(\t r)+0*0.78*sin(\t r)},{0*0.78*cos(\t r)+1*0.78*sin(\t r)});
\draw (1,-0.13)-- (1.5,-0.13);
\draw (1.5,-0.13)-- (1.75,-0.57);
\draw (1.75,-0.57)-- (1.5,-1);
\draw (1.5,-1)-- (1,-1);
\draw (1,-1)-- (0.75,-0.57);
\draw (0.75,-0.57)-- (1,-0.13);
\draw (2.5,-0.13)-- (3,-0.13);
\draw (3,-0.13)-- (3.25,-0.57);
\draw (3.25,-0.57)-- (3,-1);
\draw (3,-1)-- (2.5,-1);
\draw (2.5,-1)-- (2.25,-0.57);
\draw (2.25,-0.57)-- (2.5,-0.13);
\draw (4,-0.13)-- (4.5,-0.13);
\draw (4.5,-0.13)-- (4.75,-0.57);
\draw (4.75,-0.57)-- (4.5,-1);
\draw (4.5,-1)-- (4,-1);
\draw (4,-1)-- (3.75,-0.57);
\draw (3.75,-0.57)-- (4,-0.13);
\draw (5.5,-0.13)-- (6,-0.13);
\draw (6,-0.13)-- (6.25,-0.57);
\draw (6.25,-0.57)-- (6,-1);
\draw (6,-1)-- (5.5,-1);
\draw (5.5,-1)-- (5.25,-0.57);
\draw (5.25,-0.57)-- (5.5,-0.13);
\draw (7,-0.13)-- (7.5,-0.13);
\draw (7.5,-0.13)-- (7.75,-0.57);
\draw (7.75,-0.57)-- (7.5,-1);
\draw (7.5,-1)-- (7,-1);
\draw (7,-1)-- (6.75,-0.57);
\draw (6.75,-0.57)-- (7,-0.13);
\begin{scriptsize}
\fill [color=black] (1.5,3) circle (1.0pt);
\fill [color=black] (1,3) circle (1.0pt);
\fill [color=black] (0.75,2.57) circle (1.0pt);
\fill [color=black] (1,2.13) circle (1.0pt);
\fill [color=black] (1.5,2.13) circle (1.0pt);
\fill [color=black] (1.75,2.57) circle (1.0pt);
\fill [color=black] (3,3) circle (1.0pt);
\fill [color=black] (2.5,3) circle (1.0pt);
\fill [color=black] (2.25,2.57) circle (1.0pt);
\fill [color=black] (2.5,2.13) circle (1.0pt);
\fill [color=black] (3,2.13) circle (1.0pt);
\fill [color=black] (3.25,2.57) circle (1.0pt);
\fill [color=black] (4.5,3) circle (1.0pt);
\fill [color=black] (4,3) circle (1.0pt);
\fill [color=black] (3.75,2.57) circle (1.5pt);
\draw (3.7, 2.57) node[below]{$l_e^1$};
\fill [color=black] (4,2.13) circle (1.0pt);
\fill [color=black] (4.5,2.13) circle (1.0pt);
\fill [color=black] (4.75,2.57) circle (1.0pt);
\draw (4.6, 2.57) node[below right]{$r_e^1$};
\fill [color=black] (6,3) circle (1.0pt);
\fill [color=black] (5.5,3) circle (1.0pt);
\fill [color=black] (5.25,2.57) circle (1.0pt);
\fill [color=black] (5.5,2.13) circle (1.0pt);
\fill [color=black] (6,2.13) circle (1.0pt);
\fill [color=black] (6.25,2.57) circle (1.0pt);
\fill [color=black] (7.5,3) circle (1.0pt);
\fill [color=black] (7,3) circle (1.0pt);
\fill [color=black] (6.75,2.57) circle (1.0pt);
\fill [color=black] (7,2.13) circle (1.0pt);
\fill [color=black] (7.5,2.13) circle (1.0pt);
\fill [color=black] (7.75,2.57) circle (1.0pt);
\fill [color=black] (4.6,1.61) circle (1.5pt);
\fill [color=black] (3.9,1.61) circle (1.5pt);
\fill [color=black] (3.55,1) circle (1.5pt);
\fill [color=black] (3.9,0.4) circle (1.5pt);
\fill [color=black] (4.6,0.4) circle (1.5pt);
\fill [color=black] (4.95,1) circle (1.5pt);
\fill [color=black] (1,-1) circle (1.0pt);
\fill [color=black] (1.5,-0.13) circle (1.0pt);
\fill [color=black] (1,-1) circle (1.0pt);
\fill [color=black] (1,-0.13) circle (1.0pt);
\fill [color=black] (1.5,-1) circle (1.0pt);
\fill [color=black] (1,-0.13) circle (1.0pt);
\fill [color=black] (1.5,-1) circle (1.0pt);
\fill [color=black] (1.5,-0.13) circle (1.0pt);
\fill [color=black] (0.75,-0.57) circle (1.0pt);
\fill [color=black] (1.5,-1) circle (1.0pt);
\fill [color=black] (0.75,-0.57) circle (1.0pt);
\fill [color=black] (1.5,-0.13) circle (1.0pt);
\fill [color=black] (1.75,-0.57) circle (1.0pt);
\fill [color=black] (1,-1) circle (1.0pt);
\fill [color=black] (1.75,-0.57) circle (1.0pt);
\fill [color=black] (1,-0.13) circle (1.0pt);
\fill [color=black] (2.5,-1) circle (1.0pt);
\fill [color=black] (3,-0.13) circle (1.0pt);
\fill [color=black] (2.5,-1) circle (1.0pt);
\fill [color=black] (2.5,-0.13) circle (1.0pt);
\fill [color=black] (3,-1) circle (1.0pt);
\fill [color=black] (2.5,-0.13) circle (1.0pt);
\fill [color=black] (3,-1) circle (1.0pt);
\fill [color=black] (3,-0.13) circle (1.0pt);
\fill [color=black] (2.25,-0.57) circle (1.0pt);
\fill [color=black] (3,-1) circle (1.0pt);
\fill [color=black] (2.25,-0.57) circle (1.0pt);
\fill [color=black] (3,-0.13) circle (1.0pt);
\fill [color=black] (3.25,-0.57) circle (1.0pt);
\fill [color=black] (2.5,-1) circle (1.0pt);
\fill [color=black] (3.25,-0.57) circle (1.0pt);
\fill [color=black] (2.5,-0.13) circle (1.0pt);
\fill [color=black] (4,-1) circle (1.0pt);
\fill [color=black] (4.5,-0.13) circle (1.0pt);
\fill [color=black] (4,-1) circle (1.0pt);
\fill [color=black] (4,-0.13) circle (1.0pt);
\fill [color=black] (4.5,-1) circle (1.0pt);
\fill [color=black] (4,-0.13) circle (1.0pt);
\fill [color=black] (4.5,-1) circle (1.0pt);
\fill [color=black] (4.5,-0.13) circle (1.0pt);
\fill [color=black] (3.75,-0.57) circle (1.0pt);
\fill [color=black] (4.5,-1) circle (1.0pt);
\fill [color=black] (3.75,-0.57) circle (1.5pt);
\draw (3.7, -0.57) node[below]{$l_e^2$};
\fill [color=black] (4.5,-0.13) circle (1.0pt);
\fill [color=black] (4.75,-0.57) circle (1.0pt);
\draw (4.6, -0.57) node[below right]{$r_e^2$};
\fill [color=black] (4,-1) circle (1.0pt);
\fill [color=black] (4.75,-0.57) circle (1.0pt);
\fill [color=black] (4,-0.13) circle (1.0pt);
\fill [color=black] (5.5,-1) circle (1.0pt);
\fill [color=black] (6,-0.13) circle (1.0pt);
\fill [color=black] (5.5,-1) circle (1.0pt);
\fill [color=black] (5.5,-0.13) circle (1.0pt);
\fill [color=black] (6,-1) circle (1.0pt);
\fill [color=black] (5.5,-0.13) circle (1.0pt);
\fill [color=black] (6,-1) circle (1.0pt);
\fill [color=black] (6,-0.13) circle (1.0pt);
\fill [color=black] (5.25,-0.57) circle (1.0pt);
\fill [color=black] (6,-1) circle (1.0pt);
\fill [color=black] (5.25,-0.57) circle (1.0pt);
\fill [color=black] (6,-0.13) circle (1.0pt);
\fill [color=black] (6.25,-0.57) circle (1.0pt);
\fill [color=black] (5.5,-1) circle (1.0pt);
\fill [color=black] (6.25,-0.57) circle (1.0pt);
\fill [color=black] (5.5,-0.13) circle (1.0pt);
\fill [color=black] (1.75,-0.57) circle (1.0pt);
\fill [color=black] (2.25,-0.57) circle (1.0pt);
\fill [color=black] (3.25,-0.57) circle (1.0pt);
\fill [color=black] (3.75,-0.57) circle (1.0pt);
\fill [color=black] (4.75,-0.57) circle (1.0pt);
\fill [color=black] (5.25,-0.57) circle (1.0pt);
\fill [color=black] (7,-1) circle (1.0pt);
\fill [color=black] (7.5,-0.13) circle (1.0pt);
\fill [color=black] (7,-1) circle (1.0pt);
\fill [color=black] (7,-0.13) circle (1.0pt);
\fill [color=black] (7.5,-1) circle (1.0pt);
\fill [color=black] (7,-0.13) circle (1.0pt);
\fill [color=black] (7.5,-1) circle (1.0pt);
\fill [color=black] (7.5,-0.13) circle (1.0pt);
\fill [color=black] (6.75,-0.57) circle (1.0pt);
\fill [color=black] (7.5,-1) circle (1.0pt);
\fill [color=black] (6.75,-0.57) circle (1.0pt);
\fill [color=black] (7.5,-0.13) circle (1.0pt);
\fill [color=black] (7.75,-0.57) circle (1.0pt);
\fill [color=black] (7,-1) circle (1.0pt);
\fill [color=black] (7,-0.13) circle (1.0pt);
\fill [color=black] (6.75,-0.57) circle (1.0pt);
\fill [color=black] (6.25,-0.57) circle (1.0pt);
\fill [color=black] (0.75,-0.57) circle (1.0pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}
\caption{$T_e$ if $\varphi_e(l_e^1) \ne \varphi_e(l_e^2)$ after $\varphi_e$ has halted.}\label{fig-righttoleft}
\end{figure}


\textit{Verification:} First, note that $G$ is indeed $(n-1)$-regular and has domatic number $n$, since it consists of infinitely many $K_n^-$-chains of infinite length.  Also, $G$ is clearly computable, since to decide whether two vertices are adjacent, we simply wait until they are both used in the construction, at which point their adjacency is established forever.  

To see that $G$ contains a computable domatic $(n-1)$-partition, notice that if we color all outer vertices with color 1, and the $n-2$ inner vertices of each link with the remaining $n-2$ colors, we will produce a domatic $(n-1)$-partition.  This coloring can be done computably for this graph: as soon as a vertex is enumerated, its status as either an inner or outer vertex is determined, so it can be colored accordingly.  Connecting two chains in the construction can change a left-outer vertex to a right-outer vertex, but never an outer vertex to an inner vertex.

Finally, we argue that $G$ does not have a computable domatic $n$-partition.  For suppose it did.  Then the computable domatic $n$-partition would be $\varphi_e$ for some $e$.  There would be some finite stage at which $\varphi_e$ halts on all four of $l_e^1$, $l_e^2$, $r_e^1$ and $r_e^2$.  So at this stage, the two $K_n^-$-chains for $\varphi_e$ become a single $K_n^-$-chain.  In this single chain, $l_e^1$ is a left-outer vertex, so by Lemma \ref{chainLemma}, $\varphi_e$ must eventually color all other left-outer vertices of $T_e$ with the same color as $l_e^1$ and all right-outer vertices of $T_e$ with a different color than $l_e^1$.  However, $\varphi_e$ has already colored $l_e^2$.  If $l_e^1$ and $l_e^2$ were colored identically, then we connected the right ends of the chains, which makes $l_e^2$ a right-outer vertex of the single chain.  If $l_e^1$ and $l_e^2$ were not colored identically, then we connected the chains in such a way that $l_e^2$ is still a left-outer vertex.  In either case, we see that $\varphi_e$ cannot be a domatic $n$-partition.
\end{proof}

One way you might try to find a domatic partition is to assign colors to vertices until you get stuck, then backtrack a bit, changing colors to help dominate ``problem'' vertices.  Of course, changing a vertex might create a new problem elsewhere.  In fact, you might cause one of the neighbors of the vertex in question to no longer be dominated, and the vertex itself might become undominated.  With this as motivation, we consider {\em total domatic partitions}, in which a vertex can never help dominate itself.

Specifically, a {\em total dominating set} is a subset of $V$ such that every vertex of the graph is adjacent to a vertex in the set.  A {\em total domatic partition} is a partition of the vertices into total dominating sets, and the size of the largest total domatic partition is called the {\em total domatic number}, denoted $d_t(G)$.  Of course, for computable graphs, we can also ask about the computable total domatic number, $d_t^c(G)$.  We get a result analogous to Theorem \ref{thm-nNotn}.

\begin{theorem}\label{thm-totnNotn}
For every $n \ge 3$, there is a computable $n$-regular graph $G$ with $d_t(G) = n$ but $d_t^c(G) = n-1$.
\end{theorem} 

The proof of this theorem is similar to that Theorem \ref{thm-nNotn}.  However, in the proof of this theorem, we generate a different sort of chain.  Our proof relies on an important combinatorial fact about how these chains must be colored in any total domatic partition.  


\begin{definition} 
Define a {\em double $K_n$-link} (for $n \ge 3$) to be the graph consisting of two complete graphs on vertices $\{v_1,\ldots, v_n\}$ and $\{w_1,\ldots,w_n\}$ respectively with additional edges $(v_i, w_i)$ for $3 \le i \le n$.  A {\em double $K_n$-chain} consists of a sequence of double $K_n$-links in which the vertex $v_2$ of each link is adjacent to the $v_1$ in the next link, and the $w_2$ of each link is adjacent to the $w_1$ of the next. 
\end{definition}



For example, see Figure \ref{fig-doubleK5chain}.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.8cm,y=0.8cm]
\draw (3,4)-- (2,4);
\draw (2,4)-- (1.69,3.05);
\draw (1.69,3.05)-- (2.5,2.46);
\draw (2.5,2.46)-- (3.31,3.05);
\draw (3.31,3.05)-- (3,4);
\draw (2,4)-- (2.5,2.46);
\draw (2.5,2.46)-- (3,4);
\draw (3.31,3.05)-- (2,4);
\draw (3,4)-- (1.69,3.05);
\draw (1.69,3.05)-- (3.31,3.05);
\draw (5.25,4)-- (4.25,4);
\draw (4.25,4)-- (3.94,3.05);
\draw (3.94,3.05)-- (4.75,2.46);
\draw (4.75,2.46)-- (5.56,3.05);
\draw (5.56,3.05)-- (5.25,4);
\draw (4.25,4)-- (4.75,2.46);
\draw (4.75,2.46)-- (5.25,4);
\draw (5.56,3.05)-- (4.25,4);
\draw (5.25,4)-- (3.94,3.05);
\draw (3.94,3.05)-- (5.56,3.05);
\draw (7.5,4)-- (6.5,4);
\draw (6.5,4)-- (6.19,3.05);
\draw (6.19,3.05)-- (7,2.46);
\draw (7,2.46)-- (7.81,3.05);
\draw (7.81,3.05)-- (7.5,4);
\draw (6.5,4)-- (7,2.46);
\draw (7,2.46)-- (7.5,4);
\draw (7.81,3.05)-- (6.5,4);
\draw (7.5,4)-- (6.19,3.05);
\draw (6.19,3.05)-- (7.81,3.05);
\draw (2,0.25)-- (3,0.25);
\draw (3,0.25)-- (3.31,1.2);
\draw (3.31,1.2)-- (2.5,1.79);
\draw (2.5,1.79)-- (1.69,1.2);
\draw (1.69,1.2)-- (2,0.25);
\draw (3,0.25)-- (2.5,1.79);
\draw (2.5,1.79)-- (2,0.25);
\draw (1.69,1.2)-- (3,0.25);
\draw (2,0.25)-- (3.31,1.2);
\draw (3.31,1.2)-- (1.69,1.2);
\draw (4.25,0.25)-- (5.25,0.25);
\draw (5.25,0.25)-- (5.56,1.2);
\draw (5.56,1.2)-- (4.75,1.79);
\draw (4.75,1.79)-- (3.94,1.2);
\draw (3.94,1.2)-- (4.25,0.25);
\draw (5.25,0.25)-- (4.75,1.79);
\draw (4.75,1.79)-- (4.25,0.25);
\draw (3.94,1.2)-- (5.25,0.25);
\draw (4.25,0.25)-- (5.56,1.2);
\draw (5.56,1.2)-- (3.94,1.2);
\draw (6.5,0.25)-- (7.5,0.25);
\draw (7.5,0.25)-- (7.81,1.2);
\draw (7.81,1.2)-- (7,1.79);
\draw (7,1.79)-- (6.19,1.2);
\draw (6.19,1.2)-- (6.5,0.25);
\draw (7.5,0.25)-- (7,1.79);
\draw (7,1.79)-- (6.5,0.25);
\draw (6.19,1.2)-- (7.5,0.25);
\draw (6.5,0.25)-- (7.81,1.2);
\draw (7.81,1.2)-- (6.19,1.2);
\draw (8.75,0.25)-- (9.75,0.25);
\draw (9.75,0.25)-- (10.06,1.2);
\draw (10.06,1.2)-- (9.25,1.79);
\draw (9.25,1.79)-- (8.44,1.2);
\draw (8.44,1.2)-- (8.75,0.25);
\draw (9.75,0.25)-- (9.25,1.79);
\draw (9.25,1.79)-- (8.75,0.25);
\draw (8.44,1.2)-- (9.75,0.25);
\draw (8.75,0.25)-- (10.06,1.2);
\draw (10.06,1.2)-- (8.44,1.2);
\draw (9.75,4)-- (8.75,4);
\draw (8.75,4)-- (8.44,3.05);
\draw (8.44,3.05)-- (9.25,2.46);
\draw (9.25,2.46)-- (10.06,3.05);
\draw (10.06,3.05)-- (9.75,4);
\draw (8.75,4)-- (9.25,2.46);
\draw (9.25,2.46)-- (9.75,4);
\draw (10.06,3.05)-- (8.75,4);
\draw (9.75,4)-- (8.44,3.05);
\draw (8.44,3.05)-- (10.06,3.05);
\draw (3,4)-- (4.25,4);
\draw (5.25,4)-- (6.5,4);
\draw (7.5,4)-- (8.75,4);
\draw (3,0.25)-- (4.25,0.25);
\draw (5.25,0.25)-- (6.5,0.25);
\draw (7.5,0.25)-- (8.75,0.25);
\draw [dash pattern=on 2pt off 2pt] (9.75,0.25)-- (11,0.25);
\draw [dash pattern=on 2pt off 2pt] (9.75,4)-- (11,4);
\draw (1.69,3.05)-- (1.69,1.2);
\draw (2.5,2.46)-- (2.5,1.79);
\draw (3.31,3.05)-- (3.31,1.2);
\draw (3.94,3.05)-- (3.94,1.2);
\draw (4.75,2.46)-- (4.75,1.79);
\draw (5.56,3.05)-- (5.56,1.2);
\draw (6.19,3.05)-- (6.19,1.2);
\draw (7,2.46)-- (7,1.79);
\draw (7.81,3.05)-- (7.81,1.2);
\draw (8.44,3.05)-- (8.44,1.2);
\draw (9.25,2.46)-- (9.25,1.79);
\draw (10.06,3.05)-- (10.06,1.2);
\begin{scriptsize}
\fill [color=black] (3,4) circle (1.5pt);
\draw[color=black] (3,4) node[above] {$v_2$};
\fill [color=black] (2,4) circle (1.5pt);
\draw[color=black] (2,4) node[above] {$v_1$};
\fill [color=black] (1.69,3.05) circle (1.5pt);
\draw[color=black] (1.69,3.05) node[left] {$v_5$};
\fill [color=black] (2.5,2.46) circle (1.5pt);
\draw[color=black] (2.5,2.46) node[left] {$v_4$};
\fill [color=black] (3.31,3.05) circle (1.5pt);
\draw[color=black] (3.31,3.05) node[right] {$v_3$};
\fill [color=black] (5.25,4) circle (1.5pt);
\draw[color=black] (5.25,4) node[above] {$v_2$};
\fill [color=black] (4.25,4) circle (1.5pt);
\draw[color=black] (4.25,4) node[above] {$v_1$};
\fill [color=black] (3.94,3.05) circle (1.5pt);
%\draw[color=black] (3.94,3.05) node[above left] {$v_5^2$};
\fill [color=black] (4.75,2.46) circle (1.5pt);
%\draw[color=black] (4.75,2.46) node[below left] {$v_4^2$};
\fill [color=black] (5.56,3.05) circle (1.5pt);
%\draw[color=black] (5.56,3.05) node[below right] {$v_3^2$};
\fill [color=black] (7.5,4) circle (1.5pt);
\fill [color=black] (6.5,4) circle (1.5pt);
\fill [color=black] (6.19,3.05) circle (1.5pt);
\fill [color=black] (7,2.46) circle (1.5pt);
\fill [color=black] (7.81,3.05) circle (1.5pt);
\fill [color=black] (2,0.25) circle (1.5pt);
\draw[color=black] (2,0.25) node[below] {$w_1$};
\fill [color=black] (3,0.25) circle (1.5pt);
\draw[color=black] (3,0.25) node[below] {$w_2$};
\draw[color=black] (2.5,0.0) node[below] {$H_1$};
\fill [color=black] (3.31,1.2) circle (1.5pt);
\draw[color=black] (3.31,1.2) node[right] {$w_3$};
\fill [color=black] (2.5,1.79) circle (1.5pt);
\draw[color=black] (2.5,1.79) node[right] {$w_4$};
\fill [color=black] (1.69,1.2) circle (1.5pt);
\draw[color=black] (1.69,1.2) node[left] {$w_5$};
\fill [color=black] (4.25,0.25) circle (1.5pt);
\draw[color=black] (4.25,0.25) node[below] {$w_1$};
\fill [color=black] (5.25,0.25) circle (1.5pt);
\draw[color=black] (5.25,0.25) node[below] {$w_2$};
\draw[color=black] (4.75,0.0) node[below] {$H_2$};
\fill [color=black] (5.56,1.2) circle (1.5pt);
%\draw[color=black] (5.86,1.46) node {$C_6$};
\fill [color=black] (4.75,1.79) circle (1.5pt);
%\draw[color=black] (5.06,2.04) node {$D_6$};
\fill [color=black] (3.94,1.2) circle (1.5pt);
%\draw[color=black] (4.24,1.46) node {$E_6$};
\fill [color=black] (6.5,0.25) circle (1.5pt);
\fill [color=black] (7.5,0.25) circle (1.5pt);
\draw[color=black] (7,0.0) node[below] {$H_3$};
\fill [color=black] (7.81,1.2) circle (1.5pt);
\fill [color=black] (7,1.79) circle (1.5pt);
\fill [color=black] (6.19,1.2) circle (1.5pt);
\fill [color=black] (8.75,0.25) circle (1.5pt);
\fill [color=black] (9.75,0.25) circle (1.5pt);
\draw[color=black] (9.25,0.0) node[below] {$H_4$};
\fill [color=black] (10.06,1.2) circle (1.5pt);
\fill [color=black] (9.25,1.79) circle (1.5pt);
\fill [color=black] (8.44,1.2) circle (1.5pt);
\fill [color=black] (9.75,4) circle (1.5pt);
\fill [color=black] (8.75,4) circle (1.5pt);
\fill [color=black] (8.44,3.05) circle (1.5pt);
\fill [color=black] (9.25,2.46) circle (1.5pt);
\fill [color=black] (10.06,3.05) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}
\caption{Part of a double $K_5$-chain showing four links.}\label{fig-doubleK5chain}
\end{figure}

Following the picture, we will sometimes refer to the {\em top} and {\em bottom} $K_n$'s in a link, and refer to $v_1$, $v_2$, $w_1$, and $w_2$ as {\em outer} vertices (or sometimes {\em top-left-outer} for a $v_1$, for example).  For a finite chain, the {\em ends} refer to the vertices $v_1$ and $w_1$ of the ``first'' link and $v_2$ and $w_2$ of the ``last'' link.  To keep track of which link we are discussing, we will enumerate links as $H_i$ and then refer to their vertices as $\{v_1^i, \ldots, v_n^i, w_1^i, \ldots, w_n^i\}$.

\begin{lemma}\label{lem-doubleKnChains}
Suppose a graph $G$ with total domatic number $n \ge 3$ contains a double $K_n$-chain (either infinite or with ends adjacent to exactly one other vertex outside of the chain).  Assume $p$ is a total domatic $n$-partition of $G$ for which $p(v_1) \ne p(w_1)$ in any link in the chain. Then for {\em every} link in the chain, $p(v_1) \ne p(w_1)$ and $p(v_2) \ne p(w_2)$.  Further, for consecutive links $H_i$ and $H_j$ in the chain, we have $p(v_1^i) = p(w_2^i) = p(w_1^j) = p(v_2^j)$ and similarly $p(w_1^i) = p(v_2^i) = p(v_1^j) = p(w_2^j)$.
\end{lemma}

\begin{proof}
Let $p$ be a total domatic $n$-partition of $G$.  Note that since each vertex in the double $K_n$-chain has degree $n$, all the neighbors of a given vertex must be colored distinctly so that the vertex is dominated by all $n$ colors.  This implies that the $n$ vertices of each $K_n$ must be colored distinctly, for if two vertices were colored identically, then a third vertex of the $K_n$ would have identically colored neighbors.

Every vertex $v$ in the double $K_n$-chain is adjacent to $n-1$ vertices in its complete graph, plus one vertex $w$ outside of its complete graph.  Since $v$ must be dominated by $p(v)$, and $v$ is colored distinctly from all the other vertices in its complete graph, we must have $p(w) = p(v)$.  

Now suppose that $p(v_1^1) \ne p(w_1^1)$ in the link $H_1$, which is adjacent to $H_2$ in the chain.  Since $p(v_i^1) = p(w_i^1)$ for all $i$ such that $3 \le i \le n$ (because $v_i^1$ is adjacent to $w_i^1$), we must have $p(w_2^1) = p(v_1^1)$, since this is the only color not accounted for among $\{w_1^1, \ldots, w_n^1\}$.  Similarly, $p(v_2^1) = p(w_1^1)$.  Thus we have $p(v_2^1) \ne p(w_2^1)$.  To extend this to the next link, note that $v_2^1$ is adjacent to $v_1^2$, so $p(v_2^1) = p(v_1^2)$ and similarly $p(w_2^1) = p(w_1^2)$.  Now the same argument used for $H_1$ can be applied to $H_2$ to get $p(w_1^2) = p(v_2^2)$ and $p(v_1^2) = p(w_2^2)$.  We can then inductively extend this to all links in the chain.
\end{proof}

This lemma allows us to ensure that the top-left-outer vertex of every other link in a double $K_n$-chain must be colored identically, as long as we know that one of the corresponding bottom-left-outer vertices is colored differently.  To ensure this happens, we will build a graph $T$ consisting of four double $K_n$-chains, connected to a central double $K_n$-link in the following way.  The central link $H_0$ will be connected to links $H_1, H_2, H_3, H_4$, each the first link in their own double $K_n$-chain, by edges 
\[(v_1^0, w_1^1),~~ (v_2^0, w_1^2),~~(w_1^0, v_1^3),~~(w_2^0, v_1^4)\]
Additionally, there are edges $(v_1^1, v_1^2)$ and $(w_1^3, w_1^4)$.  See Figure \ref{fig-Tgraph}.  To keep track of the links in each of the four chains, we enumerate the links such that $H_i$ is followed by $H_{i+4}$ for all $i \ge 1$. We will call the number of links in each chain the {\em size} of $T$.


\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.65cm,y=0.65cm]
\fill[color=black,fill=black,fill opacity=0.0] (-0.451707993156,0.58368144708) -- (0.422837741383,0.58368144708) -- (0.860110608653,1.34106026996) -- (0.422837741383,2.09843909284) -- (-0.451707993156,2.09843909284) -- (-0.888980860426,1.34106026996) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (-0.430377609387,-1.76266076754) -- (0.444168125152,-1.76266076754) -- (0.881440992422,-1.00528194466) -- (0.444168125152,-0.247903121773) -- (-0.430377609387,-0.247903121773) -- (-0.867650476657,-1.00528194466) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (2.25725074554,-3.29844839892) -- (3.13179648008,-3.29844839892) -- (3.56906934735,-2.54106957604) -- (3.13179648008,-1.78369075316) -- (2.25725074554,-1.78369075316) -- (1.81997787827,-2.54106957604) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (2.25725074554,-5.51680831093) -- (3.13179648008,-5.51680831093) -- (3.56906934735,-4.75942948805) -- (3.13179648008,-4.00205066516) -- (2.25725074554,-4.00205066516) -- (1.81997787827,-4.75942948805) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (4.9235487167,-3.29844839892) -- (5.79809445124,-3.29844839892) -- (6.23536731851,-2.54106957604) -- (5.79809445124,-1.78369075316) -- (4.9235487167,-1.78369075316) -- (4.48627584943,-2.54106957604) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (4.94487910047,-5.51680831093) -- (5.81942483501,-5.51680831093) -- (6.25669770227,-4.75942948805) -- (5.81942483501,-4.00205066516) -- (4.94487910047,-4.00205066516) -- (4.5076062332,-4.75942948805) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (-3.01135404547,-3.29844839892) -- (-2.13680831093,-3.29844839892) -- (-1.69953544366,-2.54106957604) -- (-2.13680831093,-1.78369075316) -- (-3.01135404547,-1.78369075316) -- (-3.44862691274,-2.54106957604) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (-2.96869327793,-5.51680831093) -- (-2.09414754339,-5.51680831093) -- (-1.65687467612,-4.75942948805) -- (-2.09414754339,-4.00205066516) -- (-2.96869327793,-4.00205066516) -- (-3.4059661452,-4.75942948805) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (-5.74164316793,-3.29844839892) -- (-4.86709743339,-3.29844839892) -- (-4.42982456612,-2.54106957604) -- (-4.86709743339,-1.78369075316) -- (-5.74164316793,-1.78369075316) -- (-6.1789160352,-2.54106957604) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (-5.74164316793,-5.51680831093) -- (-4.86709743339,-5.51680831093) -- (-4.42982456612,-4.75942948805) -- (-4.86709743339,-4.00205066516) -- (-5.74164316793,-4.00205066516) -- (-6.1789160352,-4.75942948805) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (2.25725074554,2.11946907847) -- (3.13179648008,2.11946907847) -- (3.56906934735,2.87684790135) -- (3.13179648008,3.63422672423) -- (2.25725074554,3.63422672423) -- (1.81997787827,2.87684790135) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (4.88088794916,2.11946907847) -- (5.7554336837,2.11946907847) -- (6.19270655097,2.87684790135) -- (5.7554336837,3.63422672423) -- (4.88088794916,3.63422672423) -- (4.44361508189,2.87684790135) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (4.88088794916,4.33782899047) -- (5.7554336837,4.33782899047) -- (6.19270655097,5.09520781335) -- (5.7554336837,5.85258663623) -- (4.88088794916,5.85258663623) -- (4.44361508189,5.09520781335) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (2.25725074554,4.33782899047) -- (3.13179648008,4.33782899047) -- (3.56906934735,5.09520781335) -- (3.13179648008,5.85258663623) -- (2.25725074554,5.85258663623) -- (1.81997787827,5.09520781335) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (-3.20332749939,2.11946907847) -- (-2.32878176485,2.11946907847) -- (-1.89150889758,2.87684790135) -- (-2.32878176485,3.63422672423) -- (-3.20332749939,3.63422672423) -- (-3.64060036666,2.87684790135) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (-5.69898240039,2.11946907847) -- (-4.82443666585,2.11946907847) -- (-4.38716379858,2.87684790135) -- (-4.82443666585,3.63422672423) -- (-5.69898240039,3.63422672423) -- (-6.13625526766,2.87684790135) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (-5.69898240039,4.33782899047) -- (-4.82443666585,4.33782899047) -- (-4.38716379858,5.09520781335) -- (-4.82443666585,5.85258663623) -- (-5.69898240039,5.85258663623) -- (-6.13625526766,5.09520781335) -- cycle;
\fill[color=black,fill=black,fill opacity=0] (-3.20332749939,4.33782899047) -- (-2.32878176485,4.33782899047) -- (-1.89150889758,5.09520781335) -- (-2.32878176485,5.85258663623) -- (-3.20332749939,5.85258663623) -- (-3.64060036666,5.09520781335) -- cycle;
\draw [color=black] (-0.451707993156,0.58368144708)-- (0.422837741383,0.58368144708);
\draw [color=black] (0.422837741383,0.58368144708)-- (0.860110608653,1.34106026996);
\draw [color=black] (0.860110608653,1.34106026996)-- (0.422837741383,2.09843909284);
\draw [color=black] (0.422837741383,2.09843909284)-- (-0.451707993156,2.09843909284);
\draw [color=black] (-0.451707993156,2.09843909284)-- (-0.888980860426,1.34106026996);
\draw [color=black] (-0.888980860426,1.34106026996)-- (-0.451707993156,0.58368144708);
\draw [color=black] (-0.430377609387,-1.76266076754)-- (0.444168125152,-1.76266076754);
\draw [color=black] (0.444168125152,-1.76266076754)-- (0.881440992422,-1.00528194466);
\draw [color=black] (0.881440992422,-1.00528194466)-- (0.444168125152,-0.247903121773);
\draw [color=black] (0.444168125152,-0.247903121773)-- (-0.430377609387,-0.247903121773);
\draw [color=black] (-0.430377609387,-0.247903121773)-- (-0.867650476657,-1.00528194466);
\draw [color=black] (-0.867650476657,-1.00528194466)-- (-0.430377609387,-1.76266076754);
\draw [color=black] (2.25725074554,-3.29844839892)-- (3.13179648008,-3.29844839892);
\draw [color=black] (3.13179648008,-3.29844839892)-- (3.56906934735,-2.54106957604);
\draw [color=black] (3.56906934735,-2.54106957604)-- (3.13179648008,-1.78369075316);
\draw [color=black] (3.13179648008,-1.78369075316)-- (2.25725074554,-1.78369075316);
\draw [color=black] (2.25725074554,-1.78369075316)-- (1.81997787827,-2.54106957604);
\draw [color=black] (1.81997787827,-2.54106957604)-- (2.25725074554,-3.29844839892);
\draw [color=black] (2.25725074554,-5.51680831093)-- (3.13179648008,-5.51680831093);
\draw [color=black] (3.13179648008,-5.51680831093)-- (3.56906934735,-4.75942948805);
\draw [color=black] (3.56906934735,-4.75942948805)-- (3.13179648008,-4.00205066516);
\draw [color=black] (3.13179648008,-4.00205066516)-- (2.25725074554,-4.00205066516);
\draw [color=black] (2.25725074554,-4.00205066516)-- (1.81997787827,-4.75942948805);
\draw [color=black] (1.81997787827,-4.75942948805)-- (2.25725074554,-5.51680831093);
\draw [color=black] (4.9235487167,-3.29844839892)-- (5.79809445124,-3.29844839892);
\draw [color=black] (5.79809445124,-3.29844839892)-- (6.23536731851,-2.54106957604);
\draw [color=black] (6.23536731851,-2.54106957604)-- (5.79809445124,-1.78369075316);
\draw [color=black] (5.79809445124,-1.78369075316)-- (4.9235487167,-1.78369075316);
\draw [color=black] (4.9235487167,-1.78369075316)-- (4.48627584943,-2.54106957604);
\draw [color=black] (4.48627584943,-2.54106957604)-- (4.9235487167,-3.29844839892);
\draw [color=black] (4.94487910047,-5.51680831093)-- (5.81942483501,-5.51680831093);
\draw [color=black] (5.81942483501,-5.51680831093)-- (6.25669770227,-4.75942948805);
\draw [color=black] (6.25669770227,-4.75942948805)-- (5.81942483501,-4.00205066516);
\draw [color=black] (5.81942483501,-4.00205066516)-- (4.94487910047,-4.00205066516);
\draw [color=black] (4.94487910047,-4.00205066516)-- (4.5076062332,-4.75942948805);
\draw [color=black] (4.5076062332,-4.75942948805)-- (4.94487910047,-5.51680831093);
\draw [color=black] (-3.01135404547,-3.29844839892)-- (-2.13680831093,-3.29844839892);
\draw [color=black] (-2.13680831093,-3.29844839892)-- (-1.69953544366,-2.54106957604);
\draw [color=black] (-1.69953544366,-2.54106957604)-- (-2.13680831093,-1.78369075316);
\draw [color=black] (-2.13680831093,-1.78369075316)-- (-3.01135404547,-1.78369075316);
\draw [color=black] (-3.01135404547,-1.78369075316)-- (-3.44862691274,-2.54106957604);
\draw [color=black] (-3.44862691274,-2.54106957604)-- (-3.01135404547,-3.29844839892);
\draw [color=black] (-2.96869327793,-5.51680831093)-- (-2.09414754339,-5.51680831093);
\draw [color=black] (-2.09414754339,-5.51680831093)-- (-1.65687467612,-4.75942948805);
\draw [color=black] (-1.65687467612,-4.75942948805)-- (-2.09414754339,-4.00205066516);
\draw [color=black] (-2.09414754339,-4.00205066516)-- (-2.96869327793,-4.00205066516);
\draw [color=black] (-2.96869327793,-4.00205066516)-- (-3.4059661452,-4.75942948805);
\draw [color=black] (-3.4059661452,-4.75942948805)-- (-2.96869327793,-5.51680831093);
\draw [color=black] (-5.74164316793,-3.29844839892)-- (-4.86709743339,-3.29844839892);
\draw [color=black] (-4.86709743339,-3.29844839892)-- (-4.42982456612,-2.54106957604);
\draw [color=black] (-4.42982456612,-2.54106957604)-- (-4.86709743339,-1.78369075316);
\draw [color=black] (-4.86709743339,-1.78369075316)-- (-5.74164316793,-1.78369075316);
\draw [color=black] (-5.74164316793,-1.78369075316)-- (-6.1789160352,-2.54106957604);
\draw [color=black] (-6.1789160352,-2.54106957604)-- (-5.74164316793,-3.29844839892);
\draw [color=black] (-5.74164316793,-5.51680831093)-- (-4.86709743339,-5.51680831093);
\draw [color=black] (-4.86709743339,-5.51680831093)-- (-4.42982456612,-4.75942948805);
\draw [color=black] (-4.42982456612,-4.75942948805)-- (-4.86709743339,-4.00205066516);
\draw [color=black] (-4.86709743339,-4.00205066516)-- (-5.74164316793,-4.00205066516);
\draw [color=black] (-5.74164316793,-4.00205066516)-- (-6.1789160352,-4.75942948805);
\draw [color=black] (-6.1789160352,-4.75942948805)-- (-5.74164316793,-5.51680831093);
\draw [color=black] (2.25725074554,2.11946907847)-- (3.13179648008,2.11946907847);
\draw [color=black] (3.13179648008,2.11946907847)-- (3.56906934735,2.87684790135);
\draw [color=black] (3.56906934735,2.87684790135)-- (3.13179648008,3.63422672423);
\draw [color=black] (3.13179648008,3.63422672423)-- (2.25725074554,3.63422672423);
\draw [color=black] (2.25725074554,3.63422672423)-- (1.81997787827,2.87684790135);
\draw [color=black] (1.81997787827,2.87684790135)-- (2.25725074554,2.11946907847);
\draw [color=black] (4.88088794916,2.11946907847)-- (5.7554336837,2.11946907847);
\draw [color=black] (5.7554336837,2.11946907847)-- (6.19270655097,2.87684790135);
\draw [color=black] (6.19270655097,2.87684790135)-- (5.7554336837,3.63422672423);
\draw [color=black] (5.7554336837,3.63422672423)-- (4.88088794916,3.63422672423);
\draw [color=black] (4.88088794916,3.63422672423)-- (4.44361508189,2.87684790135);
\draw [color=black] (4.44361508189,2.87684790135)-- (4.88088794916,2.11946907847);
\draw [color=black] (4.88088794916,4.33782899047)-- (5.7554336837,4.33782899047);
\draw [color=black] (5.7554336837,4.33782899047)-- (6.19270655097,5.09520781335);
\draw [color=black] (6.19270655097,5.09520781335)-- (5.7554336837,5.85258663623);
\draw [color=black] (5.7554336837,5.85258663623)-- (4.88088794916,5.85258663623);
\draw [color=black] (4.88088794916,5.85258663623)-- (4.44361508189,5.09520781335);
\draw [color=black] (4.44361508189,5.09520781335)-- (4.88088794916,4.33782899047);
\draw [color=black] (2.25725074554,4.33782899047)-- (3.13179648008,4.33782899047);
\draw [color=black] (3.13179648008,4.33782899047)-- (3.56906934735,5.09520781335);
\draw [color=black] (3.56906934735,5.09520781335)-- (3.13179648008,5.85258663623);
\draw [color=black] (3.13179648008,5.85258663623)-- (2.25725074554,5.85258663623);
\draw [color=black] (2.25725074554,5.85258663623)-- (1.81997787827,5.09520781335);
\draw [color=black] (1.81997787827,5.09520781335)-- (2.25725074554,4.33782899047);
\draw [color=black] (-3.20332749939,2.11946907847)-- (-2.32878176485,2.11946907847);
\draw [color=black] (-2.32878176485,2.11946907847)-- (-1.89150889758,2.87684790135);
\draw [color=black] (-1.89150889758,2.87684790135)-- (-2.32878176485,3.63422672423);
\draw [color=black] (-2.32878176485,3.63422672423)-- (-3.20332749939,3.63422672423);
\draw [color=black] (-3.20332749939,3.63422672423)-- (-3.64060036666,2.87684790135);
\draw [color=black] (-3.64060036666,2.87684790135)-- (-3.20332749939,2.11946907847);
\draw [color=black] (-5.69898240039,2.11946907847)-- (-4.82443666585,2.11946907847);
\draw [color=black] (-4.82443666585,2.11946907847)-- (-4.38716379858,2.87684790135);
\draw [color=black] (-4.38716379858,2.87684790135)-- (-4.82443666585,3.63422672423);
\draw [color=black] (-4.82443666585,3.63422672423)-- (-5.69898240039,3.63422672423);
\draw [color=black] (-5.69898240039,3.63422672423)-- (-6.13625526766,2.87684790135);
\draw [color=black] (-6.13625526766,2.87684790135)-- (-5.69898240039,2.11946907847);
\draw [color=black] (-5.69898240039,4.33782899047)-- (-4.82443666585,4.33782899047);
\draw [color=black] (-4.82443666585,4.33782899047)-- (-4.38716379858,5.09520781335);
\draw [color=black] (-4.38716379858,5.09520781335)-- (-4.82443666585,5.85258663623);
\draw [color=black] (-4.82443666585,5.85258663623)-- (-5.69898240039,5.85258663623);
\draw [color=black] (-5.69898240039,5.85258663623)-- (-6.13625526766,5.09520781335);
\draw [color=black] (-6.13625526766,5.09520781335)-- (-5.69898240039,4.33782899047);
\draw [color=black] (-3.20332749939,4.33782899047)-- (-2.32878176485,4.33782899047);
\draw [color=black] (-2.32878176485,4.33782899047)-- (-1.89150889758,5.09520781335);
\draw [color=black] (-1.89150889758,5.09520781335)-- (-2.32878176485,5.85258663623);
\draw [color=black] (-2.32878176485,5.85258663623)-- (-3.20332749939,5.85258663623);
\draw [color=black] (-3.20332749939,5.85258663623)-- (-3.64060036666,5.09520781335);
\draw [color=black] (-3.64060036666,5.09520781335)-- (-3.20332749939,4.33782899047);
\draw (-2.32878176485,5.85258663623)-- (2.25725074554,5.85258663623);
\draw (-3.20332749939,5.85258663623)-- (-4.82443666585,5.85258663623);
\draw (3.13179648008,5.85258663623)-- (4.88088794916,5.85258663623);
\draw (2.25725074554,2.11946907847)-- (0.422837741383,2.09843909284);
\draw (-0.451707993156,2.09843909284)-- (-2.32878176485,2.11946907847);
\draw (0.444168125152,-1.76266076754)-- (2.25725074554,-1.78369075316);
\draw (-0.430377609387,-1.76266076754)-- (-2.13680831093,-1.78369075316);
\draw (3.13179648008,-1.78369075316)-- (4.9235487167,-1.78369075316);
\draw (3.13179648008,-5.51680831093)-- (4.94487910047,-5.51680831093);
\draw (2.25725074554,-5.51680831093)-- (-2.09414754339,-5.51680831093);
\draw (-2.96869327793,-5.51680831093)-- (-4.86709743339,-5.51680831093);
\draw (-3.01135404547,-1.78369075316)-- (-4.86709743339,-1.78369075316);
\draw (-6.13625526766,5.09520781335)-- (-6.13625526766,2.87684790135);
\draw (-5.69898240039,4.33782899047)-- (-5.69898240039,3.63422672423);
\draw (-4.82443666585,4.33782899047)-- (-4.82443666585,3.63422672423);
\draw (-4.38716379858,5.09520781335)-- (-4.38716379858,2.87684790135);
\draw (-3.64060036666,5.09520781335)-- (-3.64060036666,2.87684790135);
\draw (-3.20332749939,4.33782899047)-- (-3.20332749939,3.63422672423);
\draw (-2.32878176485,4.33782899047)-- (-2.32878176485,3.63422672423);
\draw (-1.89150889758,5.09520781335)-- (-1.89150889758,2.87684790135);
\draw (-5.69898240039,5.85258663623)-- (-4.82443666585,4.33782899047);
\draw (-6.13625526766,5.09520781335)-- (-4.38716379858,5.09520781335);
\draw (-6.13625526766,5.09520781335)-- (-4.82443666585,5.85258663623);
\draw (-6.13625526766,5.09520781335)-- (-4.82443666585,4.33782899047);
\draw (-5.69898240039,5.85258663623)-- (-5.69898240039,4.33782899047);
\draw (-5.69898240039,5.85258663623)-- (-4.38716379858,5.09520781335);
\draw (-4.82443666585,4.33782899047)-- (-4.82443666585,5.85258663623);
\draw (-5.69898240039,4.33782899047)-- (-4.82443666585,5.85258663623);
\draw (-4.38716379858,5.09520781335)-- (-5.69898240039,4.33782899047);
\draw (-6.13625526766,2.87684790135)-- (-4.82443666585,3.63422672423);
\draw (-6.13625526766,2.87684790135)-- (-4.38716379858,2.87684790135);
\draw (-6.13625526766,2.87684790135)-- (-4.82443666585,2.11946907847);
\draw (-5.69898240039,3.63422672423)-- (-5.69898240039,2.11946907847);
\draw (-5.69898240039,3.63422672423)-- (-4.82443666585,2.11946907847);
\draw (-5.69898240039,3.63422672423)-- (-4.38716379858,2.87684790135);
\draw (-4.82443666585,3.63422672423)-- (-4.82443666585,2.11946907847);
\draw (-4.82443666585,3.63422672423)-- (-5.69898240039,2.11946907847);
\draw (-5.69898240039,2.11946907847)-- (-4.38716379858,2.87684790135);
\draw (-3.64060036666,5.09520781335)-- (-2.32878176485,5.85258663623);
\draw (-3.64060036666,5.09520781335)-- (-1.89150889758,5.09520781335);
\draw (-3.64060036666,5.09520781335)-- (-2.32878176485,4.33782899047);
\draw (-3.20332749939,5.85258663623)-- (-3.20332749939,4.33782899047);
\draw (-3.20332749939,5.85258663623)-- (-2.32878176485,4.33782899047);
\draw (-3.20332749939,5.85258663623)-- (-1.89150889758,5.09520781335);
\draw (-2.32878176485,5.85258663623)-- (-2.32878176485,4.33782899047);
\draw (-2.32878176485,5.85258663623)-- (-3.20332749939,4.33782899047);
\draw (-3.20332749939,4.33782899047)-- (-1.89150889758,5.09520781335);
\draw (-0.451707993156,0.58368144708)-- (-0.430377609387,-0.247903121773);
\draw (0.422837741383,0.58368144708)-- (0.444168125152,-0.247903121773);
\draw (0.860110608653,1.34106026996)-- (0.881440992422,-1.00528194466);
\draw (-0.888980860426,1.34106026996)-- (-0.867650476657,-1.00528194466);
\draw (-3.64060036666,2.87684790135)-- (-2.32878176485,3.63422672423);
\draw (-3.64060036666,2.87684790135)-- (-1.89150889758,2.87684790135);
\draw (-3.64060036666,2.87684790135)-- (-2.32878176485,2.11946907847);
\draw (-3.20332749939,2.11946907847)-- (-2.32878176485,3.63422672423);
\draw (-3.20332749939,2.11946907847)-- (-3.20332749939,3.63422672423);
\draw (-3.20332749939,2.11946907847)-- (-1.89150889758,2.87684790135);
\draw (-2.32878176485,2.11946907847)-- (-2.32878176485,3.63422672423);
\draw (-2.32878176485,2.11946907847)-- (-3.20332749939,3.63422672423);
\draw (3.13179648008,2.11946907847)-- (4.88088794916,2.11946907847);
\draw (-3.20332749939,2.11946907847)-- (-4.82443666585,2.11946907847);
\draw (1.81997787827,5.09520781335)-- (1.81997787827,2.87684790135);
\draw (2.25725074554,4.33782899047)-- (2.25725074554,3.63422672423);
\draw (3.13179648008,4.33782899047)-- (3.13179648008,3.63422672423);
\draw (3.56906934735,5.09520781335)-- (3.56906934735,2.87684790135);
\draw (4.44361508189,5.09520781335)-- (4.44361508189,2.87684790135);
\draw (4.88088794916,4.33782899047)-- (4.88088794916,3.63422672423);
\draw (5.7554336837,4.33782899047)-- (5.7554336837,3.63422672423);
\draw (6.19270655097,5.09520781335)-- (6.19270655097,2.87684790135);
\draw (-6.1789160352,-2.54106957604)-- (-6.1789160352,-4.75942948805);
\draw (-5.74164316793,-3.29844839892)-- (-5.74164316793,-4.00205066516);
\draw (-4.86709743339,-3.29844839892)-- (-4.86709743339,-4.00205066516);
\draw (-4.42982456612,-2.54106957604)-- (-4.42982456612,-4.75942948805);
\draw (-3.44862691274,-2.54106957604)-- (-3.4059661452,-4.75942948805);
\draw (-3.01135404547,-3.29844839892)-- (-2.96869327793,-4.00205066516);
\draw (-2.13680831093,-3.29844839892)-- (-2.09414754339,-4.00205066516);
\draw (-1.69953544366,-2.54106957604)-- (-1.65687467612,-4.75942948805);
\draw (1.81997787827,-2.54106957604)-- (1.81997787827,-4.75942948805);
\draw (2.25725074554,-3.29844839892)-- (2.25725074554,-4.00205066516);
\draw (3.13179648008,-3.29844839892)-- (3.13179648008,-4.00205066516);
\draw (3.56906934735,-2.54106957604)-- (3.56906934735,-4.75942948805);
\draw (4.48627584943,-2.54106957604)-- (4.5076062332,-4.75942948805);
\draw (4.9235487167,-3.29844839892)-- (4.94487910047,-4.00205066516);
\draw (5.79809445124,-3.29844839892)-- (5.81942483501,-4.00205066516);
\draw (6.23536731851,-2.54106957604)-- (6.25669770227,-4.75942948805);
\draw (1.81997787827,5.09520781335)-- (3.13179648008,5.85258663623);
\draw (1.81997787827,5.09520781335)-- (3.56906934735,5.09520781335);
\draw (1.81997787827,5.09520781335)-- (3.13179648008,4.33782899047);
\draw (2.25725074554,4.33782899047)-- (2.25725074554,5.85258663623);
\draw (2.25725074554,4.33782899047)-- (3.13179648008,5.85258663623);
\draw (2.25725074554,4.33782899047)-- (3.56906934735,5.09520781335);
\draw (2.25725074554,5.85258663623)-- (3.56906934735,5.09520781335);
\draw (2.25725074554,5.85258663623)-- (3.13179648008,4.33782899047);
\draw (3.13179648008,4.33782899047)-- (3.13179648008,5.85258663623);
\draw (4.44361508189,5.09520781335)-- (5.7554336837,5.85258663623);
\draw (4.44361508189,5.09520781335)-- (6.19270655097,5.09520781335);
\draw (4.44361508189,5.09520781335)-- (5.7554336837,4.33782899047);
\draw (4.88088794916,4.33782899047)-- (4.88088794916,5.85258663623);
\draw (4.88088794916,4.33782899047)-- (5.7554336837,5.85258663623);
\draw (4.88088794916,4.33782899047)-- (6.19270655097,5.09520781335);
\draw (5.7554336837,4.33782899047)-- (5.7554336837,5.85258663623);
\draw (5.7554336837,4.33782899047)-- (4.88088794916,5.85258663623);
\draw (6.19270655097,5.09520781335)-- (4.88088794916,5.85258663623);
\draw (4.44361508189,2.87684790135)-- (5.7554336837,3.63422672423);
\draw (4.44361508189,2.87684790135)-- (6.19270655097,2.87684790135);
\draw (4.44361508189,2.87684790135)-- (5.7554336837,2.11946907847);
\draw (4.88088794916,3.63422672423)-- (4.88088794916,2.11946907847);
\draw (4.88088794916,3.63422672423)-- (5.7554336837,2.11946907847);
\draw (4.88088794916,3.63422672423)-- (6.19270655097,2.87684790135);
\draw (5.7554336837,3.63422672423)-- (5.7554336837,2.11946907847);
\draw (5.7554336837,3.63422672423)-- (4.88088794916,2.11946907847);
\draw (6.19270655097,2.87684790135)-- (4.88088794916,2.11946907847);
\draw (1.81997787827,2.87684790135)-- (3.13179648008,3.63422672423);
\draw (1.81997787827,2.87684790135)-- (3.56906934735,2.87684790135);
\draw (1.81997787827,2.87684790135)-- (3.13179648008,2.11946907847);
\draw (2.25725074554,3.63422672423)-- (2.25725074554,2.11946907847);
\draw (2.25725074554,3.63422672423)-- (3.13179648008,2.11946907847);
\draw (2.25725074554,3.63422672423)-- (3.56906934735,2.87684790135);
\draw (3.13179648008,3.63422672423)-- (2.25725074554,2.11946907847);
\draw (3.13179648008,3.63422672423)-- (3.13179648008,2.11946907847);
\draw (2.25725074554,2.11946907847)-- (3.56906934735,2.87684790135);
\draw (-0.888980860426,1.34106026996)-- (0.422837741383,2.09843909284);
\draw (-0.888980860426,1.34106026996)-- (0.860110608653,1.34106026996);
\draw (-0.888980860426,1.34106026996)-- (0.422837741383,0.58368144708);
\draw (-0.451707993156,0.58368144708)-- (0.422837741383,2.09843909284);
\draw (-0.451707993156,0.58368144708)-- (-0.451707993156,2.09843909284);
\draw (-0.451707993156,0.58368144708)-- (0.860110608653,1.34106026996);
\draw (0.422837741383,2.09843909284)-- (0.422837741383,0.58368144708);
\draw (0.860110608653,1.34106026996)-- (-0.451707993156,2.09843909284);
\draw (0.422837741383,0.58368144708)-- (-0.451707993156,2.09843909284);
\draw (-0.867650476657,-1.00528194466)-- (0.444168125152,-0.247903121773);
\draw (-0.867650476657,-1.00528194466)-- (0.881440992422,-1.00528194466);
\draw (-0.867650476657,-1.00528194466)-- (0.444168125152,-1.76266076754);
\draw (-0.430377609387,-1.76266076754)-- (-0.430377609387,-0.247903121773);
\draw (-0.430377609387,-1.76266076754)-- (0.444168125152,-0.247903121773);
\draw (-0.430377609387,-1.76266076754)-- (0.881440992422,-1.00528194466);
\draw (0.444168125152,-1.76266076754)-- (0.444168125152,-0.247903121773);
\draw (0.444168125152,-1.76266076754)-- (-0.430377609387,-0.247903121773);
\draw (0.881440992422,-1.00528194466)-- (-0.430377609387,-0.247903121773);
\draw (-3.44862691274,-2.54106957604)-- (-2.13680831093,-1.78369075316);
\draw (-3.44862691274,-2.54106957604)-- (-1.69953544366,-2.54106957604);
\draw (-3.44862691274,-2.54106957604)-- (-2.13680831093,-3.29844839892);
\draw (-3.01135404547,-1.78369075316)-- (-3.01135404547,-3.29844839892);
\draw (-3.01135404547,-1.78369075316)-- (-2.13680831093,-3.29844839892);
\draw (-3.01135404547,-1.78369075316)-- (-1.69953544366,-2.54106957604);
\draw (-2.13680831093,-1.78369075316)-- (-3.01135404547,-3.29844839892);
\draw (-2.13680831093,-1.78369075316)-- (-2.13680831093,-3.29844839892);
\draw (-1.69953544366,-2.54106957604)-- (-3.01135404547,-3.29844839892);
\draw (-6.1789160352,-2.54106957604)-- (-4.86709743339,-1.78369075316);
\draw (-6.1789160352,-2.54106957604)-- (-4.42982456612,-2.54106957604);
\draw (-6.1789160352,-2.54106957604)-- (-4.86709743339,-3.29844839892);
\draw (-5.74164316793,-1.78369075316)-- (-5.74164316793,-3.29844839892);
\draw (-5.74164316793,-1.78369075316)-- (-4.86709743339,-3.29844839892);
\draw (-5.74164316793,-1.78369075316)-- (-4.42982456612,-2.54106957604);
\draw (-4.86709743339,-1.78369075316)-- (-5.74164316793,-3.29844839892);
\draw (-4.86709743339,-1.78369075316)-- (-4.86709743339,-3.29844839892);
\draw (-4.42982456612,-2.54106957604)-- (-5.74164316793,-3.29844839892);
\draw (-6.1789160352,-4.75942948805)-- (-4.86709743339,-4.00205066516);
\draw (-6.1789160352,-4.75942948805)-- (-4.42982456612,-4.75942948805);
\draw (-6.1789160352,-4.75942948805)-- (-4.86709743339,-5.51680831093);
\draw (-5.74164316793,-4.00205066516)-- (-5.74164316793,-5.51680831093);
\draw (-5.74164316793,-4.00205066516)-- (-4.86709743339,-5.51680831093);
\draw (-5.74164316793,-4.00205066516)-- (-4.42982456612,-4.75942948805);
\draw (-4.86709743339,-4.00205066516)-- (-5.74164316793,-5.51680831093);
\draw (-4.86709743339,-4.00205066516)-- (-4.86709743339,-5.51680831093);
\draw (-5.74164316793,-5.51680831093)-- (-4.42982456612,-4.75942948805);
\draw (-3.4059661452,-4.75942948805)-- (-2.09414754339,-4.00205066516);
\draw (-3.4059661452,-4.75942948805)-- (-1.65687467612,-4.75942948805);
\draw (-3.4059661452,-4.75942948805)-- (-2.09414754339,-5.51680831093);
\draw (-2.96869327793,-4.00205066516)-- (-2.96869327793,-5.51680831093);
\draw (-2.96869327793,-4.00205066516)-- (-2.09414754339,-5.51680831093);
\draw (-2.96869327793,-4.00205066516)-- (-1.65687467612,-4.75942948805);
\draw (-2.09414754339,-4.00205066516)-- (-2.96869327793,-5.51680831093);
\draw (-2.09414754339,-4.00205066516)-- (-2.09414754339,-5.51680831093);
\draw (-2.96869327793,-5.51680831093)-- (-1.65687467612,-4.75942948805);
\draw (1.81997787827,-2.54106957604)-- (3.13179648008,-1.78369075316);
\draw (1.81997787827,-2.54106957604)-- (3.56906934735,-2.54106957604);
\draw (1.81997787827,-2.54106957604)-- (3.13179648008,-3.29844839892);
\draw (2.25725074554,-1.78369075316)-- (2.25725074554,-3.29844839892);
\draw (2.25725074554,-1.78369075316)-- (3.13179648008,-3.29844839892);
\draw (2.25725074554,-1.78369075316)-- (3.56906934735,-2.54106957604);
\draw (3.13179648008,-1.78369075316)-- (2.25725074554,-3.29844839892);
\draw (3.13179648008,-1.78369075316)-- (3.13179648008,-3.29844839892);
\draw (3.56906934735,-2.54106957604)-- (2.25725074554,-3.29844839892);
\draw (4.48627584943,-2.54106957604)-- (5.79809445124,-1.78369075316);
\draw (4.48627584943,-2.54106957604)-- (6.23536731851,-2.54106957604);
\draw (4.48627584943,-2.54106957604)-- (5.79809445124,-3.29844839892);
\draw (4.9235487167,-1.78369075316)-- (4.9235487167,-3.29844839892);
\draw (4.9235487167,-1.78369075316)-- (5.79809445124,-3.29844839892);
\draw (4.9235487167,-1.78369075316)-- (6.23536731851,-2.54106957604);
\draw (5.79809445124,-1.78369075316)-- (4.9235487167,-3.29844839892);
\draw (5.79809445124,-1.78369075316)-- (5.79809445124,-3.29844839892);
\draw (4.9235487167,-3.29844839892)-- (6.23536731851,-2.54106957604);
\draw (1.81997787827,-4.75942948805)-- (3.13179648008,-4.00205066516);
\draw (1.81997787827,-4.75942948805)-- (3.56906934735,-4.75942948805);
\draw (1.81997787827,-4.75942948805)-- (3.13179648008,-5.51680831093);
\draw (2.25725074554,-4.00205066516)-- (2.25725074554,-5.51680831093);
\draw (2.25725074554,-4.00205066516)-- (3.13179648008,-5.51680831093);
\draw (2.25725074554,-4.00205066516)-- (3.56906934735,-4.75942948805);
\draw (3.13179648008,-4.00205066516)-- (2.25725074554,-5.51680831093);
\draw (3.13179648008,-4.00205066516)-- (3.13179648008,-5.51680831093);
\draw (2.25725074554,-5.51680831093)-- (3.56906934735,-4.75942948805);
\draw (4.5076062332,-4.75942948805)-- (5.81942483501,-4.00205066516);
\draw (4.5076062332,-4.75942948805)-- (6.25669770227,-4.75942948805);
\draw (4.5076062332,-4.75942948805)-- (5.81942483501,-5.51680831093);
\draw (4.94487910047,-4.00205066516)-- (4.94487910047,-5.51680831093);
\draw (4.94487910047,-4.00205066516)-- (5.81942483501,-5.51680831093);
\draw (4.94487910047,-4.00205066516)-- (6.25669770227,-4.75942948805);
\draw (5.81942483501,-4.00205066516)-- (4.94487910047,-5.51680831093);
\draw (5.81942483501,-4.00205066516)-- (5.81942483501,-5.51680831093);
\draw (4.94487910047,-5.51680831093)-- (6.25669770227,-4.75942948805);
\draw (-6.13625526766,5.09520781335)-- (-5.69898240039,5.85258663623);
\draw (-5.69898240039,5.85258663623)-- (-4.82443666585,5.85258663623);
\draw (-4.82443666585,5.85258663623)-- (-4.38716379858,5.09520781335);
\draw (-4.38716379858,5.09520781335)-- (-4.82443666585,4.33782899047);
\draw (-4.82443666585,4.33782899047)-- (-5.69898240039,4.33782899047);
\draw (-5.69898240039,4.33782899047)-- (-6.13625526766,5.09520781335);
\draw (-3.64060036666,5.09520781335)-- (-3.20332749939,5.85258663623);
\draw (-3.20332749939,5.85258663623)-- (-2.32878176485,5.85258663623);
\draw (-2.32878176485,5.85258663623)-- (-1.89150889758,5.09520781335);
\draw (-1.89150889758,5.09520781335)-- (-2.32878176485,4.33782899047);
\draw (-2.32878176485,4.33782899047)-- (-3.20332749939,4.33782899047);
\draw (-3.20332749939,4.33782899047)-- (-3.64060036666,5.09520781335);
\draw (-6.13625526766,2.87684790135)-- (-5.69898240039,3.63422672423);
\draw (-5.69898240039,3.63422672423)-- (-4.82443666585,3.63422672423);
\draw (-4.82443666585,3.63422672423)-- (-4.38716379858,2.87684790135);
\draw (-4.38716379858,2.87684790135)-- (-4.82443666585,2.11946907847);
\draw (-4.82443666585,2.11946907847)-- (-5.69898240039,2.11946907847);
\draw (-5.69898240039,2.11946907847)-- (-6.13625526766,2.87684790135);
\draw (-3.64060036666,2.87684790135)-- (-3.20332749939,3.63422672423);
\draw (-3.20332749939,3.63422672423)-- (-2.32878176485,3.63422672423);
\draw (-2.32878176485,3.63422672423)-- (-1.89150889758,2.87684790135);
\draw (-1.89150889758,2.87684790135)-- (-2.32878176485,2.11946907847);
\draw (-2.32878176485,2.11946907847)-- (-3.20332749939,2.11946907847);
\draw (-3.20332749939,2.11946907847)-- (-3.64060036666,2.87684790135);
\draw (1.81997787827,5.09520781335)-- (2.25725074554,5.85258663623);
\draw (2.25725074554,5.85258663623)-- (3.13179648008,5.85258663623);
\draw (3.13179648008,5.85258663623)-- (3.56906934735,5.09520781335);
\draw (3.56906934735,5.09520781335)-- (3.13179648008,4.33782899047);
\draw (3.13179648008,4.33782899047)-- (2.25725074554,4.33782899047);
\draw (2.25725074554,4.33782899047)-- (1.81997787827,5.09520781335);
\draw (4.44361508189,5.09520781335)-- (4.88088794916,5.85258663623);
\draw (4.88088794916,5.85258663623)-- (5.7554336837,5.85258663623);
\draw (5.7554336837,5.85258663623)-- (6.19270655097,5.09520781335);
\draw (6.19270655097,5.09520781335)-- (5.7554336837,4.33782899047);
\draw (5.7554336837,4.33782899047)-- (4.88088794916,4.33782899047);
\draw (4.88088794916,4.33782899047)-- (4.44361508189,5.09520781335);
\draw (1.81997787827,2.87684790135)-- (2.25725074554,3.63422672423);
\draw (2.25725074554,3.63422672423)-- (3.13179648008,3.63422672423);
\draw (3.13179648008,3.63422672423)-- (3.56906934735,2.87684790135);
\draw (3.56906934735,2.87684790135)-- (3.13179648008,2.11946907847);
\draw (3.13179648008,2.11946907847)-- (2.25725074554,2.11946907847);
\draw (2.25725074554,2.11946907847)-- (1.81997787827,2.87684790135);
\draw (4.44361508189,2.87684790135)-- (4.88088794916,3.63422672423);
\draw (4.88088794916,3.63422672423)-- (5.7554336837,3.63422672423);
\draw (5.7554336837,3.63422672423)-- (6.19270655097,2.87684790135);
\draw (6.19270655097,2.87684790135)-- (5.7554336837,2.11946907847);
\draw (5.7554336837,2.11946907847)-- (4.88088794916,2.11946907847);
\draw (4.88088794916,2.11946907847)-- (4.44361508189,2.87684790135);
\draw (-0.888980860426,1.34106026996)-- (-0.451707993156,2.09843909284);
\draw (-0.451707993156,2.09843909284)-- (0.422837741383,2.09843909284);
\draw (0.422837741383,2.09843909284)-- (0.860110608653,1.34106026996);
\draw (0.860110608653,1.34106026996)-- (0.422837741383,0.58368144708);
\draw (0.422837741383,0.58368144708)-- (-0.451707993156,0.58368144708);
\draw (-0.451707993156,0.58368144708)-- (-0.888980860426,1.34106026996);
\draw (-0.867650476657,-1.00528194466)-- (-0.430377609387,-0.247903121773);
\draw (-0.430377609387,-0.247903121773)-- (0.444168125152,-0.247903121773);
\draw (0.444168125152,-0.247903121773)-- (0.881440992422,-1.00528194466);
\draw (0.881440992422,-1.00528194466)-- (0.444168125152,-1.76266076754);
\draw (0.444168125152,-1.76266076754)-- (-0.430377609387,-1.76266076754);
\draw (-0.430377609387,-1.76266076754)-- (-0.867650476657,-1.00528194466);
\draw (-6.1789160352,-2.54106957604)-- (-5.74164316793,-1.78369075316);
\draw (-5.74164316793,-1.78369075316)-- (-4.86709743339,-1.78369075316);
\draw (-4.86709743339,-1.78369075316)-- (-4.42982456612,-2.54106957604);
\draw (-4.42982456612,-2.54106957604)-- (-4.86709743339,-3.29844839892);
\draw (-4.86709743339,-3.29844839892)-- (-5.74164316793,-3.29844839892);
\draw (-5.74164316793,-3.29844839892)-- (-6.1789160352,-2.54106957604);
\draw (-3.44862691274,-2.54106957604)-- (-3.01135404547,-1.78369075316);
\draw (-3.01135404547,-1.78369075316)-- (-2.13680831093,-1.78369075316);
\draw (-2.13680831093,-1.78369075316)-- (-1.69953544366,-2.54106957604);
\draw (-1.69953544366,-2.54106957604)-- (-2.13680831093,-3.29844839892);
\draw (-2.13680831093,-3.29844839892)-- (-3.01135404547,-3.29844839892);
\draw (-3.01135404547,-3.29844839892)-- (-3.44862691274,-2.54106957604);
\draw (1.81997787827,-2.54106957604)-- (2.25725074554,-1.78369075316);
\draw (2.25725074554,-1.78369075316)-- (3.13179648008,-1.78369075316);
\draw (3.13179648008,-1.78369075316)-- (3.56906934735,-2.54106957604);
\draw (3.56906934735,-2.54106957604)-- (3.13179648008,-3.29844839892);
\draw (3.13179648008,-3.29844839892)-- (2.25725074554,-3.29844839892);
\draw (2.25725074554,-3.29844839892)-- (1.81997787827,-2.54106957604);
\draw (4.48627584943,-2.54106957604)-- (4.9235487167,-1.78369075316);
\draw (4.9235487167,-1.78369075316)-- (5.79809445124,-1.78369075316);
\draw (5.79809445124,-1.78369075316)-- (6.23536731851,-2.54106957604);
\draw (6.23536731851,-2.54106957604)-- (5.79809445124,-3.29844839892);
\draw (5.79809445124,-3.29844839892)-- (4.9235487167,-3.29844839892);
\draw (4.9235487167,-3.29844839892)-- (4.48627584943,-2.54106957604);
\draw (4.5076062332,-4.75942948805)-- (4.94487910047,-4.00205066516);
\draw (4.94487910047,-4.00205066516)-- (5.81942483501,-4.00205066516);
\draw (5.81942483501,-4.00205066516)-- (6.25669770227,-4.75942948805);
\draw (6.25669770227,-4.75942948805)-- (5.81942483501,-5.51680831093);
\draw (4.5076062332,-4.75942948805)-- (4.94487910047,-5.51680831093);
\draw (4.94487910047,-5.51680831093)-- (5.81942483501,-5.51680831093);
\draw (1.81997787827,-4.75942948805)-- (2.25725074554,-4.00205066516);
\draw (2.25725074554,-4.00205066516)-- (3.13179648008,-4.00205066516);
\draw (3.13179648008,-4.00205066516)-- (3.56906934735,-4.75942948805);
\draw (3.56906934735,-4.75942948805)-- (3.13179648008,-5.51680831093);
\draw (3.13179648008,-5.51680831093)-- (2.25725074554,-5.51680831093);
\draw (2.25725074554,-5.51680831093)-- (1.81997787827,-4.75942948805);
\draw (-3.4059661452,-4.75942948805)-- (-2.96869327793,-4.00205066516);
\draw (-2.96869327793,-4.00205066516)-- (-2.09414754339,-4.00205066516);
\draw (-2.09414754339,-4.00205066516)-- (-1.65687467612,-4.75942948805);
\draw (-1.65687467612,-4.75942948805)-- (-2.09414754339,-5.51680831093);
\draw (-2.09414754339,-5.51680831093)-- (-2.96869327793,-5.51680831093);
\draw (-2.96869327793,-5.51680831093)-- (-3.4059661452,-4.75942948805);
\draw (-6.1789160352,-4.75942948805)-- (-5.74164316793,-4.00205066516);
\draw (-5.74164316793,-4.00205066516)-- (-4.86709743339,-4.00205066516);
\draw (-4.86709743339,-4.00205066516)-- (-4.42982456612,-4.75942948805);
\draw (-4.42982456612,-4.75942948805)-- (-4.86709743339,-5.51680831093);
\draw (-4.86709743339,-5.51680831093)-- (-5.74164316793,-5.51680831093);
\draw (-5.74164316793,-5.51680831093)-- (-6.1789160352,-4.75942948805);
\draw (-3.20332749939,3.63422672423)-- (-1.89150889758,2.87684790135);
\begin{scriptsize}
%%%%H_0
\draw [fill=black] (-0.451707993156,0.58368144708) circle (1.5pt);

\draw [fill=black] (0.422837741383,0.58368144708) circle (1.5pt);
\draw [fill=black] (0.860110608653,1.34106026996) circle (1.5pt);

\draw [fill=black] (0.422837741383,2.09843909284) circle (1.5pt);
\draw [fill=black] (0.422837741383,2.09843909284) node[above] {$v_2^0$};

\draw [fill=black] (-0.451707993156,2.09843909284) circle (1.5pt);
\draw [fill=black] (-0.451707993156,2.09843909284) node[above] {$v_1^0$};

\draw [fill=black] (-0.888980860426,1.34106026996) circle (1.5pt);
%%%%
\draw [fill=black] (-0.430377609387,-1.76266076754) circle (1.5pt);
\draw [fill=black] (-0.430377609387,-1.76266076754) node[below] {$w_1^0$};

\draw [fill=black] (0.444168125152,-1.76266076754) circle (1.5pt);
\draw [fill=black] (0.444168125152,-1.76266076754) node[below] {$w_2^0$};

\draw [fill=black] (0.881440992422,-1.00528194466) circle (1.5pt);
\draw [fill=black] (0.444168125152,-0.247903121773) circle (1.5pt);
\draw [fill=black] (-0.430377609387,-0.247903121773) circle (1.5pt);
\draw [fill=black] (-0.867650476657,-1.00528194466) circle (1.5pt);
%%%%
\draw [fill=black] (2.25725074554,-3.29844839892) circle (1.5pt);
\draw [fill=black] (3.13179648008,-3.29844839892) circle (1.5pt);
\draw [fill=black] (3.56906934735,-2.54106957604) circle (1.5pt);
\draw [fill=black] (3.13179648008,-1.78369075316) circle (1.5pt);
\draw [fill=black] (3.13179648008,-1.78369075316) node[above] {$v_2^4$};

\draw [fill=black] (2.25725074554,-1.78369075316) circle (1.5pt);
\draw [fill=black] (2.25725074554,-1.78369075316) node[above] {$v_1^4$};

\draw [fill=black] (1.81997787827,-2.54106957604) circle (1.5pt);
%%%%
\draw [fill=black] (2.25725074554,-5.51680831093) circle (1.5pt);
\draw [fill=black] (2.25725074554,-5.51680831093) node[below] {$w_1^4$};

\draw [fill=black] (3.13179648008,-5.51680831093) circle (1.5pt);
\draw [fill=black] (3.13179648008,-5.51680831093) node[below] {$w_2^4$};

\draw [fill=black] (3.56906934735,-4.75942948805) circle (1.5pt);
\draw [fill=black] (3.13179648008,-4.00205066516) circle (1.5pt);
\draw [fill=black] (2.25725074554,-4.00205066516) circle (1.5pt);
\draw [fill=black] (1.81997787827,-4.75942948805) circle (1.5pt);
%%%%
\draw [fill=black] (4.9235487167,-3.29844839892) circle (1.5pt);
\draw [fill=black] (5.79809445124,-3.29844839892) circle (1.5pt);
\draw [fill=black] (6.23536731851,-2.54106957604) circle (1.5pt);
\draw [fill=black] (5.79809445124,-1.78369075316) circle (1.5pt);
\draw [fill=black] (5.79809445124,-1.78369075316) node[above] {$v_2^8$};

\draw [fill=black] (4.9235487167,-1.78369075316) circle (1.5pt);
\draw [fill=black] (4.9235487167,-1.78369075316) node[above] {$v_1^8$};

\draw [fill=black] (4.48627584943,-2.54106957604) circle (1.5pt);
%%%%
\draw [fill=black] (4.94487910047,-5.51680831093) circle (1.5pt);
\draw [fill=black] (4.94487910047,-5.51680831093) node[below] {$w_1^8$};

\draw [fill=black] (5.81942483501,-5.51680831093) circle (1.5pt);
\draw [fill=black] (5.81942483501,-5.51680831093) node[below] {$w_2^8$};

\draw [fill=black] (6.25669770227,-4.75942948805) circle (1.5pt);
\draw [fill=black] (5.81942483501,-4.00205066516) circle (1.5pt);
\draw [fill=black] (4.94487910047,-4.00205066516) circle (1.5pt);
\draw [fill=black] (4.5076062332,-4.75942948805) circle (1.5pt);
%%%%
\draw [fill=black] (-3.01135404547,-3.29844839892) circle (1.5pt);
\draw [fill=black] (-2.13680831093,-3.29844839892) circle (1.5pt);
\draw [fill=black] (-1.69953544366,-2.54106957604) circle (1.5pt);
\draw [fill=black] (-2.13680831093,-1.78369075316) circle (1.5pt);
\draw [fill=black] (-2.13680831093,-1.78369075316) node[above] {$v_1^3$};

\draw [fill=black] (-3.01135404547,-1.78369075316) circle (1.5pt);
\draw [fill=black] (-3.01135404547,-1.78369075316) node[above] {$v_2^3$};

\draw [fill=black] (-3.44862691274,-2.54106957604) circle (1.5pt);
%%%%
\draw [fill=black] (-2.96869327793,-5.51680831093) circle (1.5pt);
\draw [fill=black] (-2.96869327793,-5.51680831093) node[below] {$w_2^3$};

\draw [fill=black] (-2.09414754339,-5.51680831093) circle (1.5pt);
\draw [fill=black] (-2.09414754339,-5.51680831093) node[below] {$w_1^3$};

\draw [fill=black] (-1.65687467612,-4.75942948805) circle (1.5pt);
\draw [fill=black] (-2.09414754339,-4.00205066516) circle (1.5pt);
\draw [fill=black] (-2.96869327793,-4.00205066516) circle (1.5pt);
\draw [fill=black] (-3.4059661452,-4.75942948805) circle (1.5pt);
%%%%%%
\draw [fill=black] (-5.74164316793,-3.29844839892) circle (1.5pt);
\draw [fill=black] (-4.86709743339,-3.29844839892) circle (1.5pt);
\draw [fill=black] (-4.42982456612,-2.54106957604) circle (1.5pt);
\draw [fill=black] (-4.86709743339,-1.78369075316) circle (1.5pt);
\draw [fill=black] (-4.86709743339,-1.78369075316) node[above] {$v_1^7$};

\draw [fill=black] (-5.74164316793,-1.78369075316) circle (1.5pt);
\draw [fill=black] (-5.74164316793,-1.78369075316) node[above] {$v_2^7$};

\draw [fill=black] (-6.1789160352,-2.54106957604) circle (1.5pt);
%%%%
\draw [fill=black] (-5.74164316793,-5.51680831093) circle (1.5pt);
\draw [fill=black] (-5.74164316793,-5.51680831093) node[below] {$w_2^7$};

\draw [fill=black] (-4.86709743339,-5.51680831093) circle (1.5pt);
\draw [fill=black] (-4.86709743339,-5.51680831093) node[below] {$w_1^7$};

\draw [fill=black] (-4.42982456612,-4.75942948805) circle (1.5pt);
\draw [fill=black] (-4.86709743339,-4.00205066516) circle (1.5pt);
\draw [fill=black] (-5.74164316793,-4.00205066516) circle (1.5pt);
\draw [fill=black] (-6.1789160352,-4.75942948805) circle (1.5pt);
%%%%
\draw [fill=black] (2.25725074554,2.11946907847) circle (1.5pt);
\draw [fill=black] (2.25725074554,2.11946907847) node[below] {$w_1^2$};

\draw [fill=black] (3.13179648008,2.11946907847) circle (1.5pt);
\draw [fill=black] (3.13179648008,2.11946907847) node[below] {$w_2^2$};

\draw [fill=black] (3.56906934735,2.87684790135) circle (1.5pt);
\draw [fill=black] (3.13179648008,3.63422672423) circle (1.5pt);
\draw [fill=black] (2.25725074554,3.63422672423) circle (1.5pt);
\draw [fill=black] (1.81997787827,2.87684790135) circle (1.5pt);
%%%%
\draw [fill=black] (4.88088794916,2.11946907847) circle (1.5pt);
\draw [fill=black] (4.88088794916,2.11946907847) node[below] {$w_1^6$};

\draw [fill=black] (5.7554336837,2.11946907847) circle (1.5pt);
\draw [fill=black] (5.7554336837,2.11946907847) node[below] {$w_2^6$};

\draw [fill=black] (6.19270655097,2.87684790135) circle (1.5pt);
\draw [fill=black] (5.7554336837,3.63422672423) circle (1.5pt);
\draw [fill=black] (4.88088794916,3.63422672423) circle (1.5pt);
\draw [fill=black] (4.44361508189,2.87684790135) circle (1.5pt);
%%%%
\draw [fill=black] (4.88088794916,4.33782899047) circle (1.5pt);
\draw [fill=black] (5.7554336837,4.33782899047) circle (1.5pt);
\draw [fill=black] (6.19270655097,5.09520781335) circle (1.5pt);
\draw [fill=black] (5.7554336837,5.85258663623) circle (1.5pt);
\draw [fill=black] (5.7554336837,5.85258663623) node[above] {$v_2^6$};

\draw [fill=black] (4.88088794916,5.85258663623) circle (1.5pt);
\draw [fill=black] (4.88088794916,5.85258663623) node[above] {$v_1^6$};

\draw [fill=black] (4.44361508189,5.09520781335) circle (1.5pt);
%%%%
\draw [fill=black] (2.25725074554,4.33782899047) circle (1.5pt);
\draw [fill=black] (3.13179648008,4.33782899047) circle (1.5pt);
\draw [fill=black] (3.56906934735,5.09520781335) circle (1.5pt);
\draw [fill=black] (3.13179648008,5.85258663623) circle (1.5pt);
\draw [fill=black] (3.13179648008,5.85258663623) node[above] {$v_2^2$};

\draw [fill=black] (2.25725074554,5.85258663623) circle (1.5pt);
\draw [fill=black] (2.25725074554,5.85258663623) node[above] {$v_1^2$};

\draw [fill=black] (1.81997787827,5.09520781335) circle (1.5pt);
%%%%
\draw [fill=black] (-3.20332749939,2.11946907847) circle (1.5pt);
\draw [fill=black] (-3.20332749939,2.11946907847) node[below] {$w_2^1$};

\draw [fill=black] (-2.32878176485,2.11946907847) circle (1.5pt);
\draw [fill=black] (-2.32878176485,2.11946907847) node[below] {$w_1^1$};

\draw [fill=black] (-1.89150889758,2.87684790135) circle (1.5pt);
\draw [fill=black] (-2.32878176485,3.63422672423) circle (1.5pt);
\draw [fill=black] (-3.20332749939,3.63422672423) circle (1.5pt);
\draw [fill=black] (-3.64060036666,2.87684790135) circle (1.5pt);
%%%%
\draw [fill=black] (-5.69898240039,2.11946907847) circle (1.5pt);
\draw [fill=black] (-5.69898240039,2.11946907847) node[below] {$w_2^5$};

\draw [fill=black] (-4.82443666585,2.11946907847) circle (1.5pt);
\draw [fill=black] (-4.82443666585,2.11946907847) node[below] {$w_1^5$};

\draw [fill=black] (-4.38716379858,2.87684790135) circle (1.5pt);
\draw [fill=black] (-4.82443666585,3.63422672423) circle (1.5pt);
\draw [fill=black] (-5.69898240039,3.63422672423) circle (1.5pt);
\draw [fill=black] (-6.13625526766,2.87684790135) circle (1.5pt);
%%%%
\draw [fill=black] (-5.69898240039,4.33782899047) circle (1.5pt);
\draw [fill=black] (-4.82443666585,4.33782899047) circle (1.5pt);
\draw [fill=black] (-4.38716379858,5.09520781335) circle (1.5pt);
\draw [fill=black] (-4.82443666585,5.85258663623) circle (1.5pt);
\draw [fill=black] (-4.82443666585,5.85258663623) node[above] {$v_1^5$};

\draw [fill=black] (-5.69898240039,5.85258663623) circle (1.5pt);
\draw [fill=black] (-5.69898240039,5.85258663623) node[above] {$v_2^5$};

\draw [fill=black] (-6.13625526766,5.09520781335) circle (1.5pt);
%%%%
\draw [fill=black] (-3.20332749939,4.33782899047) circle (1.5pt);
\draw [fill=black] (-2.32878176485,4.33782899047) circle (1.5pt);
\draw [fill=black] (-1.89150889758,5.09520781335) circle (1.5pt);
\draw [fill=black] (-2.32878176485,5.85258663623) circle (1.5pt);
\draw [fill=black] (-2.32878176485,5.85258663623) node[above] {$v_1^1$};

\draw [fill=black] (-3.20332749939,5.85258663623) circle (1.5pt);
\draw [fill=black] (-3.20332749939,5.85258663623) node[above] {$v_2^1$};

\draw [fill=black] (-3.64060036666,5.09520781335) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}
\caption{The graph $T$ of size 2 for $n=6$.}\label{fig-Tgraph}
\end{figure}


\begin{lemma}\label{5partlemma} Let $T$ be a graph as described above, and $p$ be a total domatic $n$-partition of $T$.  Then $p(v_1^1) \ne p(w_1^1)$ or $p(v_1^2) \ne p(w_1^2)$ (or both); also $p(v_1^3) \ne p(w_1^3)$ or $p(v_1^4) \ne p(w_1^4)$ (or both). 
\end{lemma}

\begin{proof} 

Assume the negation of the lemma for the sake of contradiction.  Without loss of generality, suppose both $p(v_{1}^{1}) = p(w_{1}^{1})$ and $p(v_{1}^{2}) = p(w_{1}^{2})$. Since $v_1^1$ and $v_1^2$ are adjacent but in different complete graphs, we have $p(v_1^1) = p(v_1^2)$.  Thus we have $p(w_1^1) = p(w_1^2)$ as well.  But $w_1^1$ is adjacent to $v_1^0$, and these are in different copies of $K_n$, so $p(w_1^1) = p(v_1^0)$, and similarly $p(w_1^2) = p(v_2^0)$.  This implies that $p(v_1^0) = p(v_2^0)$, a contradiction, since these are two vertices in the same copy of a $K_n$ in a double $K_n$-link.
\end{proof}

We are now ready to prove Theorem \ref{thm-totnNotn}.

\begin{proof}[Proof of Theorem \ref{thm-totnNotn}]
The proof follows the same format as that of Theorem \ref{thm-nNotn}.  As before, we build a graph for each $\varphi_e$, except this time the graph $T_e$ will be a copy of the graph $T$ described above consisting of a central double $K_n$-link connected to four double $K_n$-chains.  As we continue to extend each of the four chains, adding a new link to each chain at each stage, we wait for $\varphi_e$ to converge on all $10n$ vertices of $H_0, \ldots, H_4$ in $T_e$.  If $\varphi_e$ never halts on these vertices, or does halt but not in a way that could be extended to a total domatic $n$-partition of all of $T_e$, we will simply continue to extend the four chains forever.  On the other hand, if $\varphi_e$ does halt on these vertices at some stage and appears to be a total domatic $n$-partition, we act as follows.

By Lemma \ref{5partlemma}, there will be $i \in \{1,2\}$ and $j \in \{3,4\}$ such that $\varphi_e(v_1^i) \ne \varphi_e(w_1^i)$ and $\varphi_e(v_1^j) \ne \varphi_e(w_1^j)$, otherwise $\varphi_e$ could not be extended to a total domatic $n$-partition.  We will connect the two chains starting with $H_i$ and $H_j$ into one chain by adding in either one or two links, depending on how $\varphi_e$ colors the vertices $v_1^i, v_1^j, w_1^i, w_1^j$.  Note that since this is happening at stage $s$, the last links in these chains are called $H_{4s+i}$ and $H_{4s+j}$.  There are two cases.

\textit{Case 1}: If $\varphi_e(v_1^i) = \varphi_e(v_1^j)$, then add a link $H' = \{v_1', \ldots, w_n'\}$ with edges \[(v_2^{4s+i}, v_1'),~(v_2^{4s+j}, v_2'),~(w_2^{4s+i}, w_1'),~(w_2^{4s+j}, w_2').\]

\textit{Case 2}: Otherwise, add two links $H'$ and $H''$ with edges
\[(v_2^{4s+i}, v_1'),~(v_2^{4s+j}, v_1''),~(w_2^{4s+i}, w_1'),~(w_2^{4s+j}, w_1''),~(v_2', v_2''),~(w_2', w_2'').\]


From this point on, continue to extend the other two chains of $T_e$ forever.

We claim that in either case, $\varphi_e$ can no longer be extended to a total domatic $n$-partition.  Suppose it could be extended to all of $T_e$.  If we are in Case 1 above, then by Lemma \ref{lem-doubleKnChains} we would then have either \[\varphi_e(v_1^i) = \varphi_e(v_1^{4s+i}) = \varphi_e(v_1^{4s+j}) = \varphi_e(v_1^j)\]
if $s$ is even, or
\[\varphi_e(v_1^i) = \varphi_e(w_1^{4s+i}) = \varphi_e(w_1^{4s+j}) = \varphi_e(v_1^j)\]
if $s$ is odd.  But it is then impossible to color $H'$ properly, since we would need $v_1'$ and $v_2'$ or $w_1'$ and $w_2'$ to be colored identically, which cannot happen in a total domatic $n$-partition.  In Case 2, again by Lemma \ref{lem-doubleKnChains}, we will either have $\varphi_e(v_1^i) = \varphi_e(v_2')$ and $\varphi_e(v_1^j) = \varphi_e(v_2'')$ or else $\varphi_e(v_1^i) = \varphi_e(w_2')$ and $\varphi_e(v_1^j) = \varphi_e(w_2'')$ (depending on the parity of $s$).  But both of these are impossible because $v_2'$ and $v_2''$ must be colored identically since they are adjacent but in different complete graphs, and similarly for $w_2'$ and $w_2''$.  Therefore $\varphi_e$ cannot be a total domatic $n$-partition, and as such, the computable total domatic number is not $n$.

However, the graph does have a computable total domatic $(n-1)$-partition: simply color all the outer vertices of all chains with color 1, and all inner vertices with the remaining $n-2$ colors.  This is clearly computable and it is easy to check that every vertex is totally dominated.

Finally, we must argue that the graph does have a (non-computable) domatic $n$-partition.  For any $T_e$ that gets extended forever as four chains, this is clear.  For a $T_e$ which has two chains connected, say without loss of generality the chains starting with $H_2$ and $H_4$, we can color $v_1^2$, $w_1^2$, $v_1^4$, and $w_1^4$ identically (the non-connected chains will have initial vertices satisfying Lemma \ref{5partlemma}).  It is easy to check that this can be extended to a total domatic $n$-partition of all of $T_e$.  Since the collection $\{T_e\}$ is pairwise disjoint, the separate total domatic $n$-partitions of each $T_e$ can be combined into a total domatic $n$-partition of $G$.
\end{proof}

Here we note that, while we proved Theorem \ref{thm-totnNotn} for $n \ge 3$, the theorem is indeed still true for $n=2$.  In fact, the proof of the theorem when $n=2$ is much simpler.  The idea of the proof is that $T_e$ will start out by consisting of a pair of two-way paths.  Since $n=2$, there are only two colors, and therefore there is only one way for $\varphi_e$ to color each path in order for the coloring to be a total domatic 2-partition: the coloring would have to be of the form $\ldots, 1, 1, 2, 2, 1, 1, 2, 2, \ldots$ (where the colors are $1$ and $2$, without loss of generality).  

In the construction of $T_e$, we begin by growing both ends of each two-way path at each stage.  As soon as $\varphi_e$ decides on a particular coloring of each of the two paths in $T_e$, we simply add new vertices and edges to connect the two paths (to form a single two-way path) in such a way that it is impossible for $\varphi_e$ to be a total domatic 2-partition of $T_e$.  For instance, if $\varphi_e$ colors one path $1,1,2,2$ and the other path $1,1,2,2$, then we could add a single new vertex to $T_e$ and connect it to the end vertices that have color 2.  Then at subsequent stages we continue to grow the other ends of $T_e$ so that $T_e$ will become a single infinite two-way path.  Of course, because of this fact, there is certainly a total domatic 2-partition of $T_e$ (it just is not $\varphi_e$).  Also, there is certainly a computable total domatic 1-partition---color everything with color 1.  If $\varphi_e$ never yields a total domatic 2-partition, then $T_e$ will be a pair of two-way infinite paths, and therefore similarly has a total domatic 2-partition, as well as a computable total domatic 1-partition.


\section{Smaller domatic partitions}\label{sect-Smaller}

A graph with domatic number $n$ necessarily has domatic partitions of all sizes less than $n$ as well: we can identify two or more of the $n$ colors resulting in fewer than $n$ disjoint dominating sets.  The smaller domatic partitions created in this fashion will be {\em divisible} in that a domatic $n$-partition can be formed by dividing single dominating sets into smaller disjoint dominating sets.  Of course not all smaller domatic partitions need be divisible; it could be that the only way to get an additional dominating set would be for two or more of the dominating sets to contribute vertices to form the new dominating set.

The existence of divisible domatic partitions suggests a potential strategy for building larger domatic partitions.  For instance, to construct a domatic $5$-partition in a graph, we might first build a divisible domatic $4$-partition, and then divide a divisible dominating set.  Maybe we start by building a divisible domatic $2$-partition, in which one set could further be divided into two disjoint dominating sets, the other into three.  Or perhaps we start by finding a minimal dominating set, one whose complement can be divided into four dominating sets.  

We will show that all these strategies are fruitless.  Not only are there regular graphs which possess no computable divisible domatic partitions of a particular type, even if such a divisible domatic partition were computable, there is no guarantee that we would be able to carry out the division effectively.

\begin{definition}
A {\em divisible domatic $k$-partition} is a domatic $k$-partition in which at least one of the sets in the partition is the disjoint union of two or more dominating sets. 
\end{definition}

\begin{definition}
Given a graph with domatic number $n$, a domatic $k$-partition is called {\em fully divisible} if each set in the $k$-partition is the union of one or more sets from some fixed domatic $n$-partition.
\end{definition}

\begin{theorem}\label{thm-nofullydivisible}
For each $n \ge 3$, there is a computable $(n-1)$-regular graph $G$ with $d(G) = n$ containing no computable fully divisible domatic 2-partition.  
\end{theorem}

\begin{proof}
The proof is similar to that of Theorem \ref{thm-nNotn}. The main difference here is what we take for the subgraphs $T_e$.  Each $T_e$ starts as three copies of the star graph $S_{n-1}$.  During the construction, we build $K_n^-$-chains starting with each leaf of each star.  We wait for $\varphi_e$ to color its three copies of $S_{n-1}$, at which point we select two chains to connect if $\varphi_e$ looks like it might be a fully divisible domatic 2-partition.  All other chains are extended forever.  

Notice that in a $K_n^-$-chain, any fully divisible domatic $k$-partition must color all left-outer vertices identically, as well as all right-outer vertices identically, since any full division requires that these be so colored.  It could be that all outer vertices (both left and right) could be the same color though.  In terms of the stars $S_{n-1}$, a fully divisible domatic $k$-partition with $k \ge 2$ must color the center vertex differently than at least one of the leaves, otherwise no full division would dominate the center vertex.  The center of each star must be colored as if it were a right-outer vertex of each chain it is attached to.

When $\varphi_e$ converges on its three stars, we only act if $\varphi_e$ looks like it could be a fully divisible domatic 2-partition.  Among the three stars, there will necessarily be two central vertices colored identically.  At least one of the leaves from each of these two stars must be assigned a different color, and the first such pair of chains gets connected.  This results in a chain with left-outer vertices not colored identically, as in Figure \ref{fig-divisibleStars}.

\begin{figure}[h]
\begin{center}
\definecolor{yqyqyq}{rgb}{0.5,0.5,0.5}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\draw (1.5,3)-- (1,3);
\draw (1,3)-- (0.75,2.57);
\draw (0.75,2.57)-- (1,2.13);
\draw (1,2.13)-- (1.5,2.13);
\draw (1.5,2.13)-- (1.75,2.57);
\draw (1.75,2.57)-- (1.5,3);
\draw (1,3)-- (1.5,2.13);
\draw (1,3)-- (1,2.13);
\draw (1.5,3)-- (1,2.13);
\draw (1.5,3)-- (1.5,2.13);
\draw (0.75,2.57)-- (1.5,3);
\draw (0.75,2.57)-- (1.5,2.13);
\draw (1.75,2.57)-- (1,3);
\draw (1.75,2.57)-- (1,2.13);
\draw (3,3)-- (2.5,3);
\draw (2.5,3)-- (2.25,2.57);
\draw (2.25,2.57)-- (2.5,2.13);
\draw (2.5,2.13)-- (3,2.13);
\draw (3,2.13)-- (3.25,2.57);
\draw (3.25,2.57)-- (3,3);
\draw (2.5,3)-- (3,2.13);
\draw (2.5,3)-- (2.5,2.13);
\draw (3,3)-- (2.5,2.13);
\draw (3,3)-- (3,2.13);
\draw (2.25,2.57)-- (3,3);
\draw (2.25,2.57)-- (3,2.13);
\draw (3.25,2.57)-- (2.5,3);
\draw (3.25,2.57)-- (2.5,2.13);
\draw (5,3)-- (4.5,3);
\draw (4.5,3)-- (4.25,2.57);
\draw (4.25,2.57)-- (4.5,2.13);
\draw (4.5,2.13)-- (5,2.13);
\draw (5,2.13)-- (5.25,2.57);
\draw (5.25,2.57)-- (5,3);
\draw (4.5,3)-- (5,2.13);
\draw (4.5,3)-- (4.5,2.13);
\draw (5,3)-- (4.5,2.13);
\draw (5,3)-- (5,2.13);
\draw (4.25,2.57)-- (5,3);
\draw (4.25,2.57)-- (5,2.13);
\draw (5.25,2.57)-- (4.5,3);
\draw (5.25,2.57)-- (4.5,2.13);
\draw (1.75,2.57)-- (2.25,2.57);
\draw (6.5,3)-- (6,3);
\draw (6,3)-- (5.75,2.57);
\draw (5.75,2.57)-- (6,2.13);
\draw (6,2.13)-- (6.5,2.13);
\draw (6.5,2.13)-- (6.75,2.57);
\draw (6.75,2.57)-- (6.5,3);
\draw (6,3)-- (6.5,2.13);
\draw (6,3)-- (6,2.13);
\draw (6.5,3)-- (6,2.13);
\draw (6.5,3)-- (6.5,2.13);
\draw (5.75,2.57)-- (6.5,3);
\draw (5.75,2.57)-- (6.5,2.13);
\draw (6.75,2.57)-- (6,3);
\draw (6.75,2.57)-- (6,2.13);
\draw (5.75,2.57)-- (5.25,2.57);
\draw [dash pattern=on 1pt off 1pt] (3.25,2.57)-- (4.25,2.57);
\draw (7.53,2.57)-- (6.75,2.57);
\draw (7.53,2.57)-- (7.29,3.32);
\draw (7.53,2.57)-- (8.17,3.04);
\draw (7.53,2.57)-- (8.17,2.11);
\draw (7.53,2.57)-- (7.3,1.82);
\draw (-0.04,2.57)-- (0.75,2.57);
\draw (-0.04,2.57)-- (0.2,3.32);
\draw (-0.04,2.57)-- (-0.68,3.03);
\draw (-0.04,2.57)-- (-0.68,2.1);
\draw (-0.04,2.57)-- (0.2,1.81);
\draw [color=yqyqyq] (0.2,1.81)-- (0.02,1.59);
\draw [color=yqyqyq] (0.02,1.59)-- (0.12,1.31);
\draw [color=yqyqyq] (0.12,1.31)-- (0.41,1.27);
\draw [color=yqyqyq] (0.41,1.27)-- (0.6,1.49);
\draw [color=yqyqyq] (0.6,1.49)-- (0.49,1.77);
\draw [color=yqyqyq] (0.49,1.77)-- (0.2,1.81);
\draw [color=yqyqyq] (0.49,1.77)-- (0.12,1.31);
\draw [color=yqyqyq] (0.02,1.59)-- (0.6,1.49);
\draw [color=yqyqyq] (0.12,1.31)-- (0.6,1.49);
\draw [color=yqyqyq] (0.49,1.77)-- (0.02,1.59);
\draw [color=yqyqyq] (0.2,1.81)-- (0.6,1.49);
\draw [color=yqyqyq] (0.49,1.77)-- (0.41,1.27);
\draw [color=yqyqyq] (0.2,1.81)-- (0.12,1.31);
\draw [color=yqyqyq] (0.41,1.27)-- (0.02,1.59);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (0.41,1.27)-- (0.5,0.98);
\draw [color=yqyqyq] (-0.68,2.1)-- (-0.95,2.18);
\draw [color=yqyqyq] (-0.95,2.18)-- (-1.15,1.98);
\draw [color=yqyqyq] (-1.15,1.98)-- (-1.08,1.71);
\draw [color=yqyqyq] (-1.08,1.71)-- (-0.81,1.63);
\draw [color=yqyqyq] (-0.81,1.63)-- (-0.61,1.83);
\draw [color=yqyqyq] (-0.61,1.83)-- (-0.68,2.1);
\draw [color=yqyqyq] (-0.68,2.1)-- (-1.15,1.98);
\draw [color=yqyqyq] (-0.68,2.1)-- (-0.81,1.63);
\draw [color=yqyqyq] (-0.61,1.83)-- (-1.08,1.71);
\draw [color=yqyqyq] (-0.61,1.83)-- (-1.15,1.98);
\draw [color=yqyqyq] (-0.61,1.83)-- (-0.95,2.18);
\draw [color=yqyqyq] (-0.81,1.63)-- (-1.15,1.98);
\draw [color=yqyqyq] (-0.81,1.63)-- (-0.95,2.18);
\draw [color=yqyqyq] (-1.08,1.71)-- (-0.95,2.18);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (-1.08,1.71)-- (-1.49,1.4);
\draw [color=yqyqyq] (-0.68,3.03)-- (-0.62,3.32);
\draw [color=yqyqyq] (-0.62,3.32)-- (-0.84,3.51);
\draw [color=yqyqyq] (-0.84,3.51)-- (-1.12,3.42);
\draw [color=yqyqyq] (-1.12,3.42)-- (-1.18,3.13);
\draw [color=yqyqyq] (-1.18,3.13)-- (-0.96,2.94);
\draw [color=yqyqyq] (-0.96,2.94)-- (-0.68,3.03);
\draw [color=yqyqyq] (-0.68,3.03)-- (-0.84,3.51);
\draw [color=yqyqyq] (-0.68,3.03)-- (-1.18,3.13);
\draw [color=yqyqyq] (-1.12,3.42)-- (-0.62,3.32);
\draw [color=yqyqyq] (-1.12,3.42)-- (-0.96,2.94);
\draw [color=yqyqyq] (-1.18,3.13)-- (-0.84,3.51);
\draw [color=yqyqyq] (-1.18,3.13)-- (-0.62,3.32);
\draw [color=yqyqyq] (-0.96,2.94)-- (-0.84,3.51);
\draw [color=yqyqyq] (-0.96,2.94)-- (-0.62,3.32);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (-1.12,3.42)-- (-1.36,3.69);
\draw [color=yqyqyq] (0.2,3.32)-- (0.46,3.37);
\draw [color=yqyqyq] (0.46,3.37)-- (0.55,3.62);
\draw [color=yqyqyq] (0.55,3.62)-- (0.37,3.82);
\draw [color=yqyqyq] (0.37,3.82)-- (0.11,3.77);
\draw [color=yqyqyq] (0.11,3.77)-- (0.03,3.52);
\draw [color=yqyqyq] (0.03,3.52)-- (0.2,3.32);
\draw [color=yqyqyq] (0.11,3.77)-- (0.46,3.37);
\draw [color=yqyqyq] (0.11,3.77)-- (0.55,3.62);
\draw [color=yqyqyq] (0.11,3.77)-- (0.2,3.32);
\draw [color=yqyqyq] (0.03,3.52)-- (0.55,3.62);
\draw [color=yqyqyq] (0.03,3.52)-- (0.46,3.37);
\draw [color=yqyqyq] (0.03,3.52)-- (0.37,3.82);
\draw [color=yqyqyq] (0.55,3.62)-- (0.2,3.32);
\draw [color=yqyqyq] (0.46,3.37)-- (0.37,3.82);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (0.37,3.82)-- (0.45,4.17);
\draw [color=yqyqyq] (7.29,3.32)-- (7.44,3.51);
\draw [color=yqyqyq] (7.44,3.51)-- (7.34,3.75);
\draw [color=yqyqyq] (7.34,3.75)-- (7.1,3.78);
\draw [color=yqyqyq] (7.1,3.78)-- (6.94,3.58);
\draw [color=yqyqyq] (6.94,3.58)-- (7.04,3.35);
\draw [color=yqyqyq] (7.04,3.35)-- (7.29,3.32);
\draw [color=yqyqyq] (7.1,3.78)-- (7.04,3.35);
\draw [color=yqyqyq] (7.1,3.78)-- (7.44,3.51);
\draw [color=yqyqyq] (7.29,3.32)-- (7.34,3.75);
\draw [color=yqyqyq] (7.29,3.32)-- (6.94,3.58);
\draw [color=yqyqyq] (6.94,3.58)-- (7.34,3.75);
\draw [color=yqyqyq] (6.94,3.58)-- (7.44,3.51);
\draw [color=yqyqyq] (7.04,3.35)-- (7.34,3.75);
\draw [color=yqyqyq] (7.04,3.35)-- (7.44,3.51);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (7.1,3.78)-- (6.9,4.14);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.17,3.04)-- (8.42,2.96);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.42,2.96)-- (8.61,3.15);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.61,3.15)-- (8.55,3.41);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.55,3.41)-- (8.29,3.48);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.29,3.48)-- (8.1,3.29);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.1,3.29)-- (8.17,3.04);
\draw [color=yqyqyq] (8.17,3.04)-- (8.29,3.48);
\draw [color=yqyqyq] (8.17,3.04)-- (8.61,3.15);
\draw [color=yqyqyq] (8.55,3.41)-- (8.1,3.29);
\draw [color=yqyqyq] (8.55,3.41)-- (8.42,2.96);
\draw [color=yqyqyq] (8.42,2.96)-- (8.29,3.48);
\draw [color=yqyqyq] (8.42,2.96)-- (8.1,3.29);
\draw [color=yqyqyq] (8.29,3.48)-- (8.61,3.15);
\draw [color=yqyqyq] (8.61,3.15)-- (8.1,3.29);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.55,3.41)-- (8.95,3.66);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.17,2.11)-- (8.14,1.86);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.14,1.86)-- (8.33,1.71);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.33,1.71)-- (8.57,1.8);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.57,1.8)-- (8.61,2.05);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.61,2.05)-- (8.41,2.21);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.41,2.21)-- (8.17,2.11);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (8.57,1.8)-- (8.97,1.51);
\draw [color=yqyqyq] (8.14,1.86)-- (8.41,2.21);
\draw [color=yqyqyq] (8.14,1.86)-- (8.61,2.05);
\draw [color=yqyqyq] (8.14,1.86)-- (8.57,1.8);
\draw [color=yqyqyq] (8.33,1.71)-- (8.17,2.11);
\draw [color=yqyqyq] (8.33,1.71)-- (8.41,2.21);
\draw [color=yqyqyq] (8.33,1.71)-- (8.61,2.05);
\draw [color=yqyqyq] (8.57,1.8)-- (8.41,2.21);
\draw [color=yqyqyq] (8.17,2.11)-- (8.61,2.05);
\draw [color=yqyqyq] (7.3,1.82)-- (7.02,1.78);
\draw [color=yqyqyq] (7.02,1.78)-- (6.92,1.53);
\draw [color=yqyqyq] (6.92,1.53)-- (7.09,1.31);
\draw [color=yqyqyq] (7.09,1.31)-- (7.36,1.35);
\draw [color=yqyqyq] (7.36,1.35)-- (7.47,1.6);
\draw [color=yqyqyq] (7.47,1.6)-- (7.3,1.82);
\draw [color=yqyqyq] (7.02,1.78)-- (7.47,1.6);
\draw [color=yqyqyq] (7.02,1.78)-- (7.36,1.35);
\draw [color=yqyqyq] (7.02,1.78)-- (7.09,1.31);
\draw [color=yqyqyq] (6.92,1.53)-- (7.3,1.82);
\draw [color=yqyqyq] (6.92,1.53)-- (7.47,1.6);
\draw [color=yqyqyq] (6.92,1.53)-- (7.36,1.35);
\draw [color=yqyqyq] (7.36,1.35)-- (7.3,1.82);
\draw [color=yqyqyq] (7.47,1.6)-- (7.09,1.31);
\draw [dash pattern=on 1pt off 1pt,color=yqyqyq] (7.09,1.31)-- (7,1);
\begin{scriptsize}
\fill [color=black] (1.5,3) circle (1.0pt);
\fill [color=black] (1,3) circle (1.0pt);
\fill [color=black] (0.75,2.57) circle (2.0pt);
\draw[color=black] (0.7,2.57) node[below] {$2$};
\fill [color=black] (1,2.13) circle (1.0pt);
\fill [color=black] (1.5,2.13) circle (1.0pt);
\fill [color=black] (1.75,2.57) circle (2.0pt);
\draw[color=black] (1.8,2.57) node[below] {$1$};
\fill [color=black] (3,3) circle (1.0pt);
\fill [color=black] (2.5,3) circle (1.0pt);
\fill [color=black] (2.25,2.57) circle (2.0pt);
\draw[color=black] (2.2,2.57) node[below] {$2$};
\fill [color=black] (2.5,2.13) circle (1.0pt);
\fill [color=black] (3,2.13) circle (1.0pt);
\fill [color=black] (3.25,2.57) circle (2.0pt);
\draw[color=black] (3.3,2.57) node[below] {$1$};
\fill [color=black] (5,3) circle (1.0pt);
\fill [color=black] (4.5,3) circle (1.0pt);
\fill [color=black] (4.25,2.57) circle (2.0pt);
\draw[color=black] (4.2,2.57) node[below] {$1$};
\fill [color=black] (4.5,2.13) circle (1.0pt);
\fill [color=black] (5,2.13) circle (1.0pt);
\fill [color=black] (5.25,2.57) circle (2.0pt);
\draw[color=black] (5.3,2.57) node[below] {$2$};
\fill [color=black] (6.5,3) circle (1.0pt);
\fill [color=black] (6,3) circle (1.0pt);
\fill [color=black] (5.75,2.57) circle (2.0pt);
\draw[color=black] (5.7,2.57) node[below] {$1$};
\fill [color=black] (6,2.13) circle (1.0pt);
\fill [color=black] (6.5,2.13) circle (1.0pt);
\fill [color=black] (6.75,2.57) circle (2.0pt);
\draw[color=black] (6.8,2.57) node[below] {$2$};
\fill [color=yqyqyq] (7.3,1.82) circle (1.0pt);
\fill [color=yqyqyq] (8.17,2.11) circle (1.0pt);
\fill [color=yqyqyq] (8.17,3.04) circle (1.0pt);
\fill [color=yqyqyq] (7.29,3.32) circle (1.0pt);
\fill [color=black] (7.53,2.57) circle (2.0pt);
\draw[color=black] (7.59,2.57) node[below] {$1$};
\fill [color=yqyqyq] (0.2,3.32) circle (1.0pt);
\fill [color=yqyqyq] (-0.68,3.03) circle (1.0pt);
\fill [color=yqyqyq] (-0.68,2.1) circle (1.0pt);
\fill [color=yqyqyq] (0.2,1.81) circle (1.0pt);
\fill [color=black] (-0.04,2.57) circle (2.0pt);
\draw[color=black] (-0.1,2.57) node[below] {$1$};
\fill [color=yqyqyq] (0.02,1.59) circle (1.0pt);
\fill [color=yqyqyq] (0.12,1.31) circle (1.0pt);
\fill [color=yqyqyq] (0.41,1.27) circle (1.0pt);
\fill [color=yqyqyq] (0.6,1.49) circle (1.0pt);
\fill [color=yqyqyq] (0.49,1.77) circle (1.0pt);
\fill [color=yqyqyq] (-0.95,2.18) circle (1.0pt);
\fill [color=yqyqyq] (-1.15,1.98) circle (1.0pt);
\fill [color=yqyqyq] (-1.08,1.71) circle (1.0pt);
\fill [color=yqyqyq] (-0.81,1.63) circle (1.0pt);
\fill [color=yqyqyq] (-0.61,1.83) circle (1.0pt);
\fill [color=yqyqyq] (-0.62,3.32) circle (1.0pt);
\fill [color=yqyqyq] (-0.84,3.51) circle (1.0pt);
\fill [color=yqyqyq] (-1.12,3.42) circle (1.0pt);
\fill [color=yqyqyq] (-1.18,3.13) circle (1.0pt);
\fill [color=yqyqyq] (-0.96,2.94) circle (1.0pt);
\fill [color=yqyqyq] (0.46,3.37) circle (1.0pt);
\fill [color=yqyqyq] (0.55,3.62) circle (1.0pt);
\fill [color=yqyqyq] (0.37,3.82) circle (1.0pt);
\fill [color=yqyqyq] (0.11,3.77) circle (1.0pt);
\fill [color=yqyqyq] (0.03,3.52) circle (1.0pt);
\fill [color=yqyqyq] (7.44,3.51) circle (1.0pt);
\fill [color=yqyqyq] (7.34,3.75) circle (1.0pt);
\fill [color=yqyqyq] (7.1,3.78) circle (1.0pt);
\fill [color=yqyqyq] (6.94,3.58) circle (1.0pt);
\fill [color=yqyqyq] (7.04,3.35) circle (1.0pt);
\fill [color=yqyqyq] (8.42,2.96) circle (1.0pt);
\fill [color=yqyqyq] (8.61,3.15) circle (1.0pt);
\fill [color=yqyqyq] (8.55,3.41) circle (1.0pt);
\fill [color=yqyqyq] (8.29,3.48) circle (1.0pt);
\fill [color=yqyqyq] (8.1,3.29) circle (1.0pt);
\fill [color=yqyqyq] (8.14,1.86) circle (1.0pt);
\fill [color=yqyqyq] (8.33,1.71) circle (1.0pt);
\fill [color=yqyqyq] (8.57,1.8) circle (1.0pt);
\fill [color=yqyqyq] (8.61,2.05) circle (1.0pt);
\fill [color=yqyqyq] (8.41,2.21) circle (1.0pt);
\fill [color=yqyqyq] (7.02,1.78) circle (1.0pt);
\fill [color=yqyqyq] (6.92,1.53) circle (1.0pt);
\fill [color=yqyqyq] (7.09,1.31) circle (1.0pt);
\fill [color=yqyqyq] (7.36,1.35) circle (1.0pt);
\fill [color=yqyqyq] (7.47,1.6) circle (1.0pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}
\caption{For two stars with identically colored central vertex (in this case 1) connect chains with initial vertex {\em not} colored 1 (in this case, 2).}\label{fig-divisibleStars}
\end{figure}

Finally, we argue that the graph so built does indeed have domatic number $n$.  Each $T_e$ is either the disjoint union of three stars each with infinite $K_n^-$-chains attached to each of their leaves, or the same only with two of the stars attached by a finite $K_n^-$-chain.  In the first case, it is easy to produce a domatic $n$-partition: color the center of each star with color 1 and all the leaves with color 2, which are all left-outer vertices of the first link in their chains.  The inner vertices of all links get colors 3 through $n$, the right-outer vertices get color 1, and the left-outer vertices color 2. For the second case, we can use this same coloring for two of the stars, but for one of the stars connected by the $K_n^-$-chain, we simply swap all instances of color 1 and color 2.  Note that while we can do this, $\varphi_e$ cannot, because it does not know which pair of stars will be connected when it colors the vertices of the stars.
\end{proof}

\begin{corollary}
For each $n \ge 3$ and $k$ such that $2 \le k < n$, there is a computable $(n-1)$-regular graph $G$ with $d(G) = n$ containing no computable fully divisible domatic $k$-partition.  
\end{corollary}

\begin{proof}
Consider a graph $G$ as guaranteed by Theorem \ref{thm-nofullydivisible}.  For any $k$ such that $2 \le k < n$, $G$ does not have a computable fully divisible domatic $k$-partition either.  For if it did, we could identify colors $1$ through $k-1$ to get a fully divisible domatic $2$-partition.  Identifying colors can be done computably (in the algorithm for the $k$-partition, just replace the colors 1 through $k-1$ with color 1), so this would result in a {\em computable} fully divisible domatic $2$ partition. 
\end{proof}

Even if we could find a fully divisible domatic partition, we might still not be able to use this to build up to a full domatic partition of the graph.  

\begin{theorem}
For any $n \ge 3$ and $k < n$, there is a computable $(n - 1)$-regular graph $G$ with $d(G) = n$ which has a computable fully divisible domatic $k$-partition but no computable domatic $n$-partition.
\end{theorem}

\begin{proof}
The graph constructed in Theorem \ref{thm-nNotn} works, as the computable domatic $(n - 1)$-partition constructed there is in fact fully divisible.  This shows that the theorem holds for $k = n-1$.  For smaller $k$, we get a computable fully divisible domatic $k$-partition by identifying colors.
\end{proof}

Although there is no hope of finding these ``nice'' divisible domatic partitions of smaller size, there still might be computable domatic partitions of sub-optimal size.  Certainly any computable graph with $d(G) = n$, for $n \ge 2$, has a computable domatic 2-partition.  For computable regular graphs, we can do better.

\begin{theorem} \label{n_squared}
Suppose $G$ is a computable $k$-regular graph with domatic number $k + 1$.  Then $G$ has a computable domatic $n$-partition for all $n$ satisfying $n^2 \le k + 1$.
\end{theorem}

\begin{proof}
We show the theorem for $k \geq 8$.  (The theorem clearly holds for $k < 8$, because every computable graph without isolated vertices already has a computable domatic $2$-partition, as the current authors showed in \cite{jlm}.)  We also fix $n$ to be maximal (such that $n^2 \leq k + 1$), because the theorem will then clearly follow for smaller values of $n$.  Also, assume $G$ is connected.  At the end of the proof, we will describe how to modify the procedure in case we do not know that $G$ is connected.

As a point of terminology, we say that a set $S$ of vertices is \emph{dominated} by a set of colors $\{c_1, \ldots, c_l\}$ if all of the vertices of $S$ are colored with $\{c_1, \ldots, c_l\}$ and each vertex of $S$ that has all of its neighbors in $S$ is dominated under this coloring.  Note that any finite set $S$ of vertices of $G$ can be dominated by $\{1, \ldots, k + 1\}$.  Indeed, since $G$ has a domatic $(k+1)$-partition by hypothesis, we will eventually find one that works on $S$ by searching through all possible partitions of $S$ (because each such partition is itself finite).  We will use this fact throughout the procedure.

\textit{Procedure}:  Define the \emph{disk centered at vertex $v$ of radius $r$} to be the set $D_v(r) = \{u \in V \st d(u, v) \leq r\}$, where $d(u, v)$ is the length of the shortest path from $u$ to $v$.  For brevity, we write $D_{v_0}(r)$ as $D(r)$.  At stage $0$, color $D(4)$ so that it is dominated by colors $\{1, \ldots, k + 1\}$, ensuring that vertex $v_0$ is colored with color $1$.  We declare $v_0$ to be permanently colored (with color $1$), while the other vertices have only been temporarily colored.  Let $r_1 = 2$, and assume inductively that the vertices of $D(r_s + 2) \setminus D(r_s - 2)$ were temporarily colored with colors $\{1, \ldots, k+1\}$ at stage $s - 1$.  We color vertices at stage $s$ as follows.  (Some vertices will be permanently colored, while others will only be temporarily colored.)

Define $A_s = D(r_s)$ and $B_s = D(r_s + 6) \setminus A_s$.  Color the set $D(r_s + 6) \setminus D(r_s - 2)$ so that it is dominated by colors $\{1, \ldots, k + 1\}$.  Note, we have \emph{doubly colored} some of the vertices (i.e., the $2$ layers of $A_s$ closest to $B_s$ and the $2$ layers of $B_s$ closest to $A_s$, constituting a $4$-wide band of doubly-colored vertices): they have their original coloring (the temporary coloring from the previous stage), which we will say is \emph{preferred} by $A_s$, and the coloring just given, \emph{preferred} by $B_s$.  Denote the double-color of each such vertex by $x | y$, where $x$ is the color preferred by $A_s$ and $y$ is the color preferred by $B_s$.

Resolve the color of each doubly-colored vertex $v$ by choosing one color for $v$ as follows.  First, to change from $k+1$ down to $n$ colors, we will convert to congruent numbers modulo $n$.  Specifically, define $f:\{1, \ldots, k + 1\} \to \{1, \ldots, n\}$ by $f(c) = (c - 1 \mod n) + 1$.  (This way, colors $1$ through $n$ stay the same, color $n + 1$ goes to $1$, $n + 2$ to $2$, $n + 3$ to $3$, and so on.)  Use the following rules to resolve $v$, which is currently colored $x | y$.

\begin{itemize}
\item If $x, y \leq n$, color it $f(x)$ if $v \in A_s$ and $f(y)$ if $v \in B_s$.
\item If $x, y > n$, color it $f(x)$.
\item Otherwise, color it $f(x)$ if $x \leq n$ and $f(y)$ if $y \leq n$.
\end{itemize}

After resolving a doubly-colored vertex, declare it permanently colored.  Next, let $r_{s + 1} = r_s + 4$, and proceed to stage $s + 1$.  Note that $A_{s + 1} = D(r_{s + 1})$ will include all the vertices that are permanently colored, as well as two layers previously just (temporarily) colored by $B_s$.  For stage $s + 1$, informally speaking, we consider all the coloring done by the old $B$ to be the one preferred by the new $A$, as the new $B$ will be coloring a fresh set of vertices, including all the non-permanently (i.e., temporarily) colored vertices in the new $A$.

\textit{Verification}:  Let $v\in V$ and $s$ be the earliest stage of the procedure after which $v$ and all of its neighbors have been permanently colored.  We show that $v$ is dominated by the end of stage $s$ and therefore will remain dominated.  Consider the two possible cases that could occur just before the resolution of the doubly-colored vertices: (1) some vertices among $v$ and its neighbors are \emph{singly colored} (i.e., colored, but not doubly colored), and (2) none of these vertices are singly colored.  In each case, fix $c \in \{1, \ldots, n\}$.  We show that $v$ or one of its neighbors gets permanently colored $c$.

\textit{Case 1}: At least one vertex (among $v$ and its neighbors) is singly colored.  Note that because of the width of the doubly-colored region, $v$ and its neighbors are either all in $A_s$ or all in $B_s$.  If they are all in $B_s$, then one of them would be colored $c$ by $B_s$ and would thus get resolved to $c$ by rule 1.  Also note that, by our procedure, they cannot all be in $B_s$ (in fact, none of them is in $B_s$).  However, this might happen in the general case (when $G$ is not necessarily connected), as we will see when describing that procedure below.

Now assume they are all in $A_s$, and assume that no singly-colored vertex (among $v$ and its neighbors) is colored $c$.  Again, because of the width of the doubly-colored region in each stage, all of the singly-colored vertices must have been doubly colored (and thus received their permanent color) during the previous stage (i.e., stage $s - 1$) and were in the set $B_{s - 1}$.  So, since none of them resolved to the color $c$, the preference of $B_{s - 1}$ for each of those vertices during stage $s - 1$ could not have been $c$.  Hence $B_{s - 1}$ must have preferred a different vertex $w$ (among $v$ and its neighbors) to be colored $c$ (in order to dominate $v$, since $v$ was also in $B_{s - 1}$ at the time), namely one of the now doubly-colored vertices (in stage $s$).  Since $A_s$ and $B_{s - 1}$ color vertices in the same way and $w \in A_s$, $w$ will resolve to $c$.

\textit{Case 2}: All vertices (among $v$ and its neighbors) are doubly colored.  Then for every $j$, with $0 \leq j < n$, there is a vertex among $v$ and its neighbors that is colored $(c + jn) | y_j$ for $n$ distinct colors $y_j$.  Now if any $y_j > n$, then $(c + jn) | y_j$ resolves to $f(c + jn) = c$ by the second or third rule for resolving doubly-colored vertices. On the other hand, if $y_j \leq n$ for all $0 \le j < n$, then one of these $n$ vertices (with color of the form $(c + jn) | y_j$) has $y_j = c$ and hence gets resolved to $c$ by the first or third rule.  Thus at least one of the vertices resolves to $c$ as desired.

\textit{Not Necessarily Connected Graphs}: If we are not promised that $G$ is connected, we perform the same procedure as in the connected case, only now we enumerate $G$ and decide if the current vertex $v$ of $G$ should be part of the existing sets $A$ and $B$, or if it should be put in its own pair of sets $A$ and $B$, disjoint from the original pair.  This decision will depend on the distance of $v$ from $A$ and $B$.

As the procedure progresses, there will be disjoint collections of vertices with their own sets $A$ and $B$.  We will call each such collection of vertices a \emph{system}.  These disjoint systems will get resolved (via the double-coloring routine) simultaneously.  As they are increasing in size, however, they might eventually collide, at which point the part of the procedure that enlarges $B$ will now enlarge it to a size that fully encompasses all colliding systems.  This will result in all systems that were involved in the collision to combine into one common system.  Note that some vertices in this enlarged $B$ might not be a part of the double-coloring and will thus still have colors outside of $\{1, \ldots, n\}$.  So we will change the colors of the vertices of $B$, except those in its outer $4$ layers, according to the following rule (which will narrow down from $k + 1$ to $n$ colors and will give these vertices their permanent color).
\begin{center}
If the vertex has color $x$, change it to $f(x)$.
\end{center}
Eventually the procedure will have been successfully performed on each component of $G$.
\end{proof}

We observe the following modification of Theorem \ref{n_squared}, which uses a more efficient procedure for small values of $k$ (i.e., for $k \leq 23$).  However, it quickly becomes less efficient, requiring an exponential gap between the domatic numbers.  Indeed, our original procedure only requires a polynomial (in fact, quadratic) gap.

\begin{theorem} \label{expResult}
Suppose $G$ is a computable $k$-regular graph with domatic number $k+1$.  Then $G$ has a computable domatic $n$-partition for all $n$ satisfying $2^n - 1 \le k + 1$.
\end{theorem}

\begin{proof}
Let $k \geq 6$, and let $n$ be maximal such that $2^n - 1 \leq k + 1$.  Consider a computable graph that is $k$-regular and has domatic number $k + 1$.  Also assume that the graph is connected; as before, the procedure can be modified to deal with graphs that are not necessarily connected.  We perform a similar procedure as in Theorem \ref{n_squared}, but we use a different set of rules to resolve the doubly-colored vertices.  Also, due to a counting argument needed in the verification, we make a slight change to the placement of the doubly-colored region of vertices in each stage.  In the original procedure, the doubly-colored regions in consecutive stages were adjacent to each other; this time around, we must keep them apart by a distance of two vertices.

\textit{Procedure}:  At stage $0$, perform the coloring as we did in Theorem \ref{n_squared} but now on $D(6)$ instead of $D(4)$.  We proceed just as before but with one additional condition.  Whenever coloring a set $S$ of vertices, ensure that any vertex $v$ outside of $S$ but adjacent to at least two vertices in $S$ is not adjacent to two vertices of the same color, according to the coloring just performed.  This can be ensured by coloring the union of $S$ and all such $v$, then suppressing the coloring of those $v$.  Let $r_1 = 4$, and proceed inductively to stage $s$ as follows.  Let $A_s = D(r_s)$ and $B_s = D(r_s + 8) \setminus A_s$.  Color the set $D(r_s + 8) \setminus D(r_s - 2)$ as we similarly did in the original procedure, creating a $4$-wide band of doubly-colored vertices.  Different from the original procedure, however, we additionally have a $2$-wide band of \emph{singly-colored} vertices (in $A_s$) that have yet to receive a permanent color.

Now use the new set of rules shown below to resolve (i.e., permanently color) these bands of singly- and doubly-colored vertices.  As a point of terminology, we say that a color $c$ is \emph{present} if the vertex in question is either singly colored and has color $c$ or is doubly colored and has color of the form $c | x$ or $x | c$ for some $x$.  The rules are as follows, where $2 \leq c \leq n - 1$.
\begin{itemize}
\item[1.] If $1$ is present, color it $1$.
\item[$c$.] If at least one of $2^{c - 1}, \ldots, 2^c - 1$ is present (with $1, \ldots, 2^{c - 1} - 1$ not), color it $c$.
\item[$n$.] Otherwise, color it $n$.
\end{itemize}
Notice, the pattern here is that each rule uses one more color than the previous rules combined.  Indeed, rule $c$ uses $2^c - 1 - 2^{c - 1} + 1 = 2^{c - 1}$ colors, and the sum of the number of colors used in the previous rules is $\sum_{i = 1}^{c - 1}2^{i - 1} = 2^{c - 1} - 1$.  Finally, let $r_{s + 1} = r_s + 6$, and proceed to stage $s + 1$.

\textit{Verification}:  We show that each $v \in V$ is eventually dominated.  For a fixed $v \in V$, wait for the first stage $s$ after which $v$ and all of its neighbors have been permanently colored.  First, we consider the case where none of the vertices (among $v$ and its neighbors) received its permanent color prior to stage $s$ (namely, in stage $s - 1$).  So all of the vertices received their permanent color in stage $s$.  Moreover, they received their permanent color at a time they were being either singly colored by one of the two sets $A_s$ and $B_s$, or doubly colored by these two sets.  In fact, such vertices that are singly colored are not being colored by $B_s$.  But this could happen in the general case, i.e., when $G$ is not necessarily connected, so it is important to consider this possibility.

Let $A = A_s$ and $B = B_s$, and note the following two facts.  First, neither $A$ nor $B$ colors any two vertices (among $v$ and its neighbors) the same, because we ensured that whenever a set of vertices was being dominated, no vertex adjacent to at least two vertices in the set could have two neighbors colored the same.  Second, note that either $A$ colors all $k + 1$ vertices or $B$ colors all $k + 1$ vertices (or both sets color all of them).  Note, $B$ does not color all the vertices without $A$ also coloring them all, but this could happen in the general case.
Therefore, for the sake of this verification, we can consider all $k + 1$ vertices to be ``doubly colored.''  Specifically, each vertex has color of the form $x | y$, where $A$ prefers $x$ and $B$ prefers $y$, and we use a blank color when a set has not actually colored the vertex.  Also, because of our second observation above, we know that either $A$ colors none of the vertices blank or $B$ colors none of them blank.

We can now show that for each color $1 \leq c \leq n$, at least one of the vertices among $v$ and its neighbors gets permanently colored $c$.  When making this claim we will say, ``there is a $c$.''  First, it is clear that there is a $1$, because by the discussion above there is a vertex for which $1$ is present (i.e., colored $1 | x$ or $x | 1$ for some color $x$).  So it gets permanently colored $1$ by rule 1.  Now let $2 \leq c \leq n$.  Consider rule $c$, and let $p$ be the sum of the number of colors used in all of the previous rules.  By our earlier observation (immediately following the list of $n$ rules, shown above), the number of colors used in rule $c$ is $p + 1$.  We also mentioned earlier that one of the two sets $A$ and $B$ colors none of the vertices blank; say it is $A$, without loss of generality.  Therefore, $A$ will use each of the aforementioned $p + 1$ colors; that is, $A$ will color $p + 1$ vertices with the colors from rule $c$ in such a way that it colors no two vertices the same.  However, $B$ can only use colors from the previous rules on at most $p$ of those $p + 1$ vertices.  So there is at least one vertex with a color present from rule $c$ but no color present from any of the previous rules.  Hence there is a $c$ by rule $c$.

Finally, in the case where at least one of the vertices (among $v$ and its neighbors) received its permanent color prior to stage $s$, the same argument works by using $A = A_{s - 1}$ and $B = B_{s - 1}$.  Notice that in this case, $v$ and its neighbors are too far away to be doubly colored by the ``current'' pair of sets, i.e., $A_s$ and $B_s$, so the double coloring will only be done by the ``previous'' pair of sets, $A_{s - 1}$ and $B_{s - 1}$.
\end{proof}


\section{Conclusion and Open Questions}\label{sec-Questions}

As it stands right now, we know that there are computable regular graphs with domatic number $n$ but computable domatic number $n-1$, and that every computable regular graph with domatic number $n$ has a computable domatic partition of size at least $\lfloor\sqrt{n}\rfloor$.  It would be nice to shrink this gap.  We suspect that Theorem \ref{thm-nNotn} could be improved to build a computable regular graph with domatic number $n$ but no computable domatic $n-1$ partition.  However, notice that the method we used to diagonalize against all computable functions relied on our ability to force all domatic $n$-partitions to color specific vertices identically.  We can be sure that this particular approach will not help in separating $d(G)$ and $d^c(G)$ further.

\begin{proposition}
If a graph $G$ has domatic number $n \ge 3$, then for any vertices $u$ and $v$ of $G$, there is a domatic $(n-1)$-partition in which $u$ and $v$ are colored identically, and a domatic $(n-1)$-partition in which $u$ and $v$ are colored differently. 
\end{proposition}

\begin{proof}
Consider the domatic $n$-partitions of $G$.  If there exists partitions in which $u$ and $v$ are colored differently, then we can get a domatic $(n-1)$-partition in which $u$ and $v$ are colored differently by eliminating another color, and a domatic $(n-1)$-partition in which $u$ and $v$ are colored identically by changing the color of $u$ (for all similarly colored vertices) to the color of $v$.  On the other hand, if all domatic $n$-partitions put $u$ and $v$ into the same color, the we can get a domatic $(n-1)$-partition in which $u$ and $v$ are identically colored by eliminating a different color.  To get a domatic $(n-1)$-partition in which $u$ and $v$ are differently colored, take a color other than that of $u$ and $v$ and merge it with the color of $u$ and $v$.  Then $v$ and all of its neighbors will be dominated by $v$'s color at least {\em twice}: once by $v$ and once by the vertices whose color we just changed.  Thus we can recolor $v$ without losing domination.
\end{proof}

Similar arguments can show that there is in fact very little we can force all domatic $(n-1)$-partitions to do when the graph has domatic number $n$.  There are two obvious exceptions to this general principle.  First, by the pigeonhole principle, given $n$ vertices, we know that every domatic $(n-1)$-partition will put at least two of these into the same class.  Second, since it is possible to force $n$ vertices to belong to $n$ different classes in a domatic $n$-partition, we can force that among $n$ vertices, every domatic $(n-1)$-partitions will put exactly two of them into the same class.  To summarize:

\begin{proposition}
There is a graph $G$ with domatic number $n$ containing a set of $n$ vertices $\{v_0, v_1, \ldots, v_{n-1}\}$ such that every domatic $(n-1)$-partition of $G$ will put exactly two of these $n$ vertices into the same class.
\end{proposition}

Whether this observation can be leveraged to further separate $d(G)$ and $d^c(G)$ is not clear.  Thus we ask:

\begin{question}
Is there a computable regular graph $G$ with $d(G) = n$ but $d^c(G) = n-2$?  In general, for a fixed $n$, what is the largest $d(G) - d^c(G)$ can be?
\end{question}

Also not clear is what role the minimal degree of our graphs play.  The graph in Theorem \ref{thm-nNotn} is domatically full in that the domatic number is as large as possible based on the minimal degree of the graph, so we have that the minimal degree of $G$ is $n-1$, equal to the computable domatic number.  Can we force the computable domatic number to be {\em less} than the minimal degree?  The answer is yes if the graphs need not be regular - we can build a graph in which the minimal degree is arbitrarily larger than the domatic number, using a generalization of Zelinka's argument in \cite{zelinka} and independently build a graph with large domatic number but computable domatic number 2.  If we can further separate $d(G)$ and $d^c(G)$ for regular computable graphs, then a similar argument can separate the minimal degree and the computable domatic number.  But perhaps answering the following question would be easier.

\begin{question}
Is there a computable $n$-regular graph $G$ with $d(G) = n$ and $d^c(G) = n-1$.
\end{question}

Along similar lines, we would like to know what happens when we relax our insistence that our graphs be regular, but still require that there was a procedure to find all neighbors of a given vertex.  In particular, regularity is required for the proof of Theorem \ref{n_squared}, but perhaps a different approach would allow us to find a small non-trivial domatic partition.

\begin{question}
Suppose $G$ is a highly computable graph (i.e., there is an algorithm which produces all the neighbors of any given vertex) with domatic number $n \ge 4$.  For which such $n$ (if any) must there be a computable domatic $k$-partition with $k \ge 3$?  
\end{question}

Finally, another direction to take this line of inquiry is to consider other kinds of domatic partitions.  We have already seen that considering total domatic partitions gives at least some separation between classical and computable domatic number, but there are other notions of domatic partition which might be interesting to consider.  For example, the {\em independent domatic number}, denoted $d_i(G)$ is defined in \cite{fundom} to be the size of the largest partition of vertices into sets which are both domatic and independent.  Another: the {\em paired domatic number}, denoted $d_{pr}(G)$ is the size of the largest partition into dominating sets, for which the induced subgraph of each contains a perfect matching (this notion is also defined in \cite{fundom}).  We can, of course, consider the computable analogues of these invariants, $d_i^c(G)$ and $d_{pr}^c(G)$, and ask how they can differ from the classical invariants. 

Quite by accident, the graph constructed in Theorem \ref{thm-nNotn} has $d_i(G) = n$ but $d_i^c(G) = n-1$: the domatic $n$ partition of $G$ happens to be an independent domatic partition, and the computable domatic $(n-1)$-partition is a computable independent domatic $(n-1)$-partition.  It also just so happens that the total domatic $n$-partition and computable total domatic $(n-1)$-partition in the graph built for Theorem \ref{thm-totnNotn} are also paired domatic partitions, so we have an example of a computable graph with $d_{pr}(G) = n$ but $d_{pr}^c(G) = n-1$.  We wonder if this is a coincidence.  

Classically we have $d(G) \ge d_i(G)$ and $d(G) \ge d_t(G) \ge d_{pr}(G)$.  It would be interesting to see what happens to these inequalities when we consider the computable analogues.  For example, is there a computable graph $G$ for which $d_t(G) = d_{pr}(G)$ but $d_t^c(G) > d_{pr}^c(G)$?  Could we have $d_t(G) > d_{pr}(G)$ but $d_t^c(G) = d_{pr}^c(G)$?  How extreme could the inequalities be?  We summarize these questions as follows.

\begin{question}
Let $G$ be a computable graph.  Let $d_x$ and $d_y$ be two comparable notions of domatic number.  Then what, if anything, does $d_x(G) - d_y(G)$ imply about $d_x^c(G) - d_y^c(G)$?
\end{question}

\subsection*{Acknowledgements}
The authors would like to thank the anonymous reviewer for several helpful suggestions.



%\bibliographystyle{plain}
%\bibliography{FindingDomaticPartitions}

% \bib, bibdiv, biblist are defined by the amsrefs package.
\begin{bibdiv}
\begin{biblist}
\normalsize
\bib{bean}{article}{
      author={Bean, Dwight~R.},
       title={Effective coloration},
        date={1976},
        ISSN={0022-4812},
     journal={J. Symbolic Logic},
      volume={41},
      number={2},
       pages={469\ndash 480},
 %     review={\MR{0416889 (54 \#4952)}},
}

\bib{bertossi}{article}{
      author={Bertossi, Alan~A.},
       title={On the domatic number of interval graphs},
        date={1988},
        ISSN={0020-0190},
     journal={Inform. Process. Lett.},
      volume={28},
      number={6},
       pages={275\ndash 280},
         url={http://dx.doi.org/10.1016/0020-0190(88)90173-1},
     % review={\MR{963513 (89h:68054)}},
}

\bib{feige}{inproceedings}{
      author={Feige, Uriel},
      author={Halld{\'o}rsson, Magn{\'u}s~M.},
      author={Kortsarz, Guy},
       title={Approximating the domatic number},
        date={2000},
   booktitle={Proceedings of the {T}hirty-{S}econd {A}nnual {ACM} {S}ymposium
  on {T}heory of {C}omputing},
   publisher={ACM, New York},
       pages={134\ndash 143 (electronic)},
         url={http://dx.doi.org/10.1145/335305.335321},
    %  review={\MR{2114526}},
}

\bib{gareyjohnson}{book}{
      author={Garey, Michael~R.},
      author={Johnson, David~S.},
       title={Computers and intractability},
   publisher={W. H. Freeman and Co., San Francisco, Calif.},
        date={1979},
        ISBN={0-7167-1045-5},
  %      note={A guide to the theory of NP-completeness, A Series of Books in
%  the Mathematical Sciences},
    %  review={\MR{519066 (80g:68056)}},
}

\bib{fundom}{book}{
      author={Haynes, Teresa~W.},
      author={Hedetniemi, Stephen~T.},
      author={Slater, Peter~J.},
       title={Fundamentals of domination in graphs},
      series={Monographs and Textbooks in Pure and Applied Mathematics},
   publisher={Marcel Dekker, Inc., New York},
        date={1998},
      volume={208},
        ISBN={0-8247-0033-3},
    %  review={\MR{1605684 (2001a:05112)}},
}

\bib{jlm}{article}{
      author={Jura, Matthew},
      author={Levin, Oscar},
      author={Markkanen, Tyler},
       title={Domatic partitions of computable graphs},
        date={2014},
        ISSN={0933-5846},
     journal={Arch. Math. Logic},
      volume={53},
      number={1-2},
       pages={137\ndash 155},
         url={http://dx.doi.org/10.1007/s00153-013-0359-2},
    %  review={\MR{3151402}},
}

\bib{kaplan}{article}{
      author={Kaplan, Haim},
      author={Shamir, Ron},
       title={The domatic number problem on some perfect graph families},
        date={1994},
        ISSN={0020-0190},
     journal={Inform. Process. Lett.},
      volume={49},
      number={1},
       pages={51\ndash 56},
         url={http://dx.doi.org/10.1016/0020-0190(94)90054-X},
    %  review={\MR{1264925 (94k:05188)}},
}

\bib{riege}{article}{
      author={Riege, Tobias},
      author={Rothe, J{\"o}rg},
       title={Complexity of the exact domatic number problem and of the exact
  conveyor flow shop problem},
        date={2006},
        ISSN={1432-4350},
     journal={Theory Comput. Syst.},
      volume={39},
      number={5},
       pages={635\ndash 668},
         url={http://dx.doi.org/10.1007/s00224-004-1209-8},
   %   review={\MR{2256634 (2007i:68030)}},
}

\bib{rogers}{book}{
      author={Rogers, Hartley, Jr.},
       title={Theory of recursive functions and effective computability},
     edition={Second},
   publisher={MIT Press, Cambridge, MA},
        date={1987},
        ISBN={0-262-68052-1},
    %  review={\MR{886890 (88b:03059)}},
}

\bib{schmerl}{article}{
      author={Schmerl, James~H.},
       title={Recursive colorings of graphs},
        date={1980},
        ISSN={0008-414X},
     journal={Canad. J. Math.},
      volume={32},
      number={4},
       pages={821\ndash 830},
         url={http://dx.doi.org/10.4153/CJM-1980-062-7},
   %   review={\MR{590647 (81m:03054)}},
}

\bib{soare}{book}{
      author={Soare, Robert~I.},
       title={Recursively enumerable sets and degrees},
      series={Perspectives in Mathematical Logic},
   publisher={Springer-Verlag, Berlin},
        date={1987},
        ISBN={3-540-15299-7},
         url={http://dx.doi.org/10.1007/978-3-662-02460-7},
    %    note={A study of computable functions and computably generated sets},
   %   review={\MR{882921 (88m:03003)}},
}

\bib{zelinka}{article}{
      author={Zelinka, Bohdan},
       title={Domatic number and degrees of vertices of a graph},
        date={1983},
        ISSN={0025-5173},
     journal={Math. Slovaca},
      volume={33},
      number={2},
       pages={145\ndash 147},
   %   review={\MR{699083 (85b:05146)}},
}

\end{biblist}
\end{bibdiv}


  
\end{document}
