exercise07.10.tex

\paragraph{Exercise 7.10}
\begin{enumerate}
  \item[(a)] We know that there is a colouring of $G$ with 3 colors such that no
  two adjacent vertices have the same color. Let $G$ be colored with the 3 colors
  red, blue and green such that the just mentioned condition holds. We can observe
  that the vertices of each triangle have three different colors. Let us now change
  the color of every green vertex to blue. Now, we have a 2-colored graph such
  that the vertices of each triangle have two different colors. Hence, there
  exists a coloring of $G$ with two colors such that no triangle is monochromatic.

  \item[(b)] Let $C$ be any 3-coloring of the graph $G$ such that no two adjacent
  vertices have the same color. Let $V_b,V_r$ and $V_g$ be the vertex setx colored
  by blue, red and green colors, respectively. Clearly, each of them is an independent
  set. Hence any traingle in the graph must have a vertex in each of these sets. \\
  Let $C'$ be the arbitrary 2-coloring of $G$ from which the algorithm starts.
  Suppose that $C'$ uses blue and red colors only. Let us compare $C'$ with $C$.
  If the algorithm reaches a state starting with $C'$ such that all vertices in $V_b$
  are colored blue and all vertices in $V_r$ are colored red, then clearly, no
  triangle can be monochromatic irrespective of the color of the vertices in $V_g$. \\
  Thus, we can measure the distance of the \textit{goal} coloring from the present
  one using the number of miscolored blue and red vertices, i.e., $v \in V_b$ such
  that color($v$) = red and $v'\in V_r$ such that color($v'$) = blue. \\
  Now, at each step, the algorithm chooses a monochromatic triangle at random.
  It can either be a \textbf{rrr} or \textbf{bbb} triangle. If it flips the color
  of a vertex $\in V_g$, the distance from the \textit{goal} coloring remains the
  same. In the case when it is a \textbf{rrr} triangle, if it flips the color of
  a vertex $\in V_b$, the number of miscoloured vertices decreases. On the other
  hand, if the flip occurs for a vertex $\in V_r$, this nuzmber increases.
  Similar situations exists in the \textbf{bbb} case. \\
  The algorithm, thus, can be represented as performing a random walk on a $n$
  vertex line, where $n = |G|$ with the probabilities shown in Figure \ref{fig:graph}.
  \begin{figure}[h]
    \setlength\intextsep{0pt}
    \centering
    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,semithick]
      \node[state] (A)              {...};
      \node[state] (B) [right of=A] {$i$};
      \node[state] (C) [right of=B] {...};
      \node[state] (D) [right of=C] {goal};

      \path (A) edge [loop above] node {1/3} (A)
                edge [bend left]  node {1/3} (B)
            (B) edge [loop above] node {1/3} (B)
                edge [bend left]  node {1/3} (A)
                edge [bend left]  node {1/3} (C)
            (C) edge [loop above] node {1/3} (C)
                edge [bend left]  node {1/3} (B)
                edge [bend left]  node {1/3} (D)
            (D) edge [loop above] node {1}   (D);
    \end{tikzpicture}
    \caption{vertex line}
    \label{fig:graph}
  \end{figure}
  Hence, the expected time to complete is the expected time to reach the end
  vertex starting from any vertex of the vertex line. In the worst case, it can
  start from the other end of the line when all vertices are micolored. \\
  The recurrence for the expected time is,
  \begin{align*}
    h_{i,\text{goal}}
      &= \frac{1}{3} \left( h_{i,\text{goal}} + h_{i-1,\text{goal}} + h_{i+1,\text{goal}} \right) \\
      &= \frac{1}{2} \left( h_{i-1,\text{goal}} + h_{i+1,\text{goal}} \right).
  \end{align*}
  From this, we get $h_{0,\text{goal}} = O\left(n^2 \right)$. Hence, the expected
  running time of the algorithm is $O\left( n^2 \right)$.
\end{enumerate}