Students sometimes struggle with proving that a given problem belongs to class P. Though generally capable of providing an algorithm $\mathcal{A}$ that at least approximates correction, great difficulty is encountered in $a.$ proving its correctness and $b.$ proving its belonging to P.
Acquaintance with examples may serve him at least as much as a theoretical familiarity with the problem at hand. Thus, I present here a simple and straight-forward algorithm that decides whether a graph $G = (V, E)$ has $\chi(G) \leq 2$. An advanced student will probably be familiar with the effective procedure instantiated by this algorithm. Thus, this entry is directed to students just becoming acquainted with computational complexity.
Our task is to provide an algorithm that decides if any given graph can be properly colored with two colors. Let us first describe the algorithm from a theoretical perspective. At the end, I shall provide a C implementation that relies on my cGraphs API.
Our algorithm will take an arbitrary non-colored vertex as the root of its connected component and color it with $1$. Within each connected component, it runs BFS from the given root to explore it. Each time BFS pivots over a vertex $p \in V$ and enqueues its neighbors, the algorithm also colors each neighbor with $3 - c(p)$, thus ensuring that all colors are in the range $\{ 1, 2 \} $.
Importantly, the color of any given vertex will be fully determined by the parity of its level in the BFS tree. Since the root at level zero is set to $1$, all vertices in the second level are colored with $2$, those in the third with $1$, and so on.
$$ \begin{align*} &j := 0\\ &\textbf{while } j < n \textbf{ do } \\ &\qquad r := \text{arbitrary non-colored vertex} \\ &\qquad c(r) := 1 \\ &\qquad j := j + 1 \\ &\qquad queue = \left\{ r \right\} \\ & \qquad\textbf{while } queue \neq \emptyset \textbf{ do } \\ & \qquad \qquad p := pop(queue) \\ &\qquad\qquad \textbf{for } x \in \Gamma(p) \textbf{ do } \\ & \qquad \qquad \qquad \textbf{if } x \text{ not colored} \textbf{ do} \\ &\qquad \qquad \qquad \qquad c(x) := 3 - c(p)\\ &\qquad \qquad \qquad \qquad j := j + 1;\\ &\qquad \qquad \qquad \qquad push(queue, x)\\ &\qquad\qquad\qquad\textbf{fi}\\ &\qquad\qquad \textbf{od}\\ &\qquad\textbf{od}\\ &\textbf{od}\\ &\textbf{for } \left\{ x, y \right\} \in E \textbf{ do } \\ &\qquad \textbf{if } c(x) = c(y) ~ \textbf{do } return \textbf{ False fi} \\ &\textbf{od}\\ &return \textbf{ True} \end{align*} $$
The inner while runs BFS with a slight modification to color vertices when they are enqueued and is thus $O(m)$. It is executed per each connected component and the number of connected components is $O(n)$. $\therefore $ The algorithm is polynomial.
That the algorithm correctly decides that a graph is two-colorable is trivial. To prove that it also correctly decides that a graph is not two-colorable, we shall prove a negative answer entails the graph contains an odd cycle.
Assume the algorithm was executed over $G = (V, E)$ and returned $\textbf{False}$. Then there is some $\overrightarrow{xy} \in E$, in a particular connected component $\mathcal{C} \subseteq G$, s.t. $c(x) = c(y)$. Let us presume, without loss of generality, that $x$ was enqueued before $y$. Let us denote with $r$ the root of $\mathcal{C}$ from which BFS was ran.
Assume $x$ enqueues $y$. Then $c(y) = 3 - c(x) \neq c(x)$, a contradiction. Then $x$ does not enqueue $y$. But this can only happen if, when $x$ is the at front of the queue, $y$ was already enqueued by some other vertex.
In particular, there is a vertex $w$ that is the vertex of greater level common to $x$ and $y$ in the BFS tree—i.e. the vertex from which $x$ and $y$ diverge—. Let $\eta(w)$ be the level of $w$ in the BFS tree.
Consider the cycle $w \ldots x y \ldots w$, which exists because all these vertices belong to $\mathcal{C}$. There are $\eta(x) - \eta(w)$ edges from $w$ to $x$, and $\eta(y) - \eta(w)$ edges from $y$ to $w$. There is one extra edge for $xy$. The total amount is then
\begin{align*} \eta(x) - \eta(w) + \eta(y) - \eta(w) + 1 &= \eta(x) + \eta(y) - 2\eta(w) + 1 \end{align*}
By assumption, $\eta(x)$ and $\eta(y)$ are both greater than $\eta(w)$. $\therefore $ $\eta(x) + \eta(y) > 2\eta(w)$ and length of the path is greater than zero (sanity check).
Since $c(x) = c(y)$, $\eta(x) \equiv \eta(y) \mod 2$ and therefore $\eta(x) + \eta(y)$ is even. Then the length of the cycle is odd.
$\therefore $ $C_{2k+1} \subseteq \mathcal{C}$ and $\chi(G) \geq 3$.
A C implementation of this algorithm may go as follows.
bool twoColorable(Graph G){
struct Queue* Q = createQueue();
enQueue(Q, 0);
setColor(1, 0, G);
while (!isEmpty(Q)){
u32 pivot = pop(Q);
u32 pivotColor = getColor(pivot, G);
u32 degree = Degree(pivot, G);
for (u32 i = 0; i < degree; i++){
u32 iNeighbor = Neighbor(i, pivot, G);
if (getColor(iNeighbor, G) != 0){
continue;
}
enQueue(Q, iNeighbor);
setColor(3 - pivotColor, iNeighbor, G);
}
}
printf("\n\n");
for (u32 i = 0; i < 2*NumberOfEdges(G); i++){
struct EdgeSt e = getEdge(i, G);
color cX = getColor(e.x, G), cY = getColor(e.y, G);
if (cX == cY){
return false;
}
}
return true;
}
One can make this more efficient by checking for improper colorings during the BFS run. However, proving the correctness of this slightly different algorithm is different.
bool twoColorable(Graph G){
struct Queue* Q = createQueue();
enQueue(Q, 0);
setColor(1, 0, G);
while (!isEmpty(Q)){
u32 pivot = pop(Q);
u32 pivotColor = getColor(pivot, G);
u32 degree = Degree(pivot, G);
for (u32 i = 0; i < degree; i++){
u32 iNeighbor = Neighbor(i, pivot, G);
if (getColor(iNeighbor, G) == 0){
enQueue(Q, iNeighbor);
setColor(3 - pivotColor, iNeighbor, G);
}
if (getColor(iNeighbor, G) == pivotColor){
return false;
}
}
}
return true;
}