\problemdata                                                             
        {counting-25} % latex-friendly label for the prob.
        {Counting; Graph Coloring} % The topic(s) of the problem content.  
        {Radhika Nagpal} % Source (if known)         
        {S02 cp7W} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}
A possible algorithm for checking if a graph is 3-colorable is to
enumerate all possible 3 color assignments to the nodes of the graph
and then test each assignment to see if it is a valid coloring
(reminder a valid coloring is one where no two adjacent vertices have
the same color).

Let $G$ be a $n$ node graph with vertices labelled $v_1$ through
$v_n$. Let the set of colors $C=\{R,G,B\}$.

\begin{problemparts}
\problempart In how many different ways can you assign colors from $C$
to the nodes of $G$?

\solution{$3^n$}

\problempart Enumerate all the possible color assignments for a 3-node
graph with vertices $v1,v2,v3$ using the colors $C$.

\problempart There are much easier ways to check if a graph can be
colored with one color or two colors. Therefore we are really only
interested in color assignments that use {\em exactly} 3 colors. How
many such color assignments are there?

\solution{Need to substract $\leq 2$ color assignments from the total
number of $\leq 3$ color assignments from part (a). There are three
sets of two colors RG, RB, BG. For any set, the number of possible
color assignments is $2^n$. So the total number of assignments that
use exactly 3 colors is $3^n - 3.2^n$. VERIFY}

%% BETTER IDEA: easy to check 1 colors and 2 colorability therefore I
%% am actually only interested in color assignments with exactly 3
%% colors. How many color assignments are there that use exactly three
%% colors?

%% Then remove the redundant colors...but only for the three case
%% (division rule)

\noindent A valid 3-coloring of a graph is a assignment of three
colors to the nodes such that no two adjacent nodes have the same
color. One algorithm for determining whether the graph $G$ can be
colored with 3 colors is to test all possible 3 color
assignments. However several of the assignments from above are
redundant. For example, for a 4-node graph with nodes $v_1, v_2, v_3,
v_4$, the color assignment $RRRR$ is the same as the color assignment
$GGGG$ or $BBBB$. Similarly the color assignment $RGRG$ is the same as
assigning the nodes the colors $GRGR$, $BRBR$, $RBRB$, $GBBG$,
$BGGB$. By the ``same'' we mean that if one assignment is not valid,
the other ones are guaranteed to fail. In general a color assignment
is redundant, if we already checked another assignment than can be
acheived by swapping the names of the colors.


\problempart For a 3-node graph with vertices $v1,v2,v3$ , list all
possible color assignments. List only the non redundant color
assignments

\problempart (*\footnote{I do not know the solution to this
problem. It actually looks quite hard. But that's just my first
assesment, I may be wrong...} Count the number of different ways can
you assign colors from $C$ to the nodes of $G$, after removing all
redundant mappings as described above?

\solution{
Still in the works...
}

\problempart Test your answer to part (b) for a three node graph. (In
other words, list the number of non-redundant RGB colorings and see if
your answer from above yields the same number. This is a good strategy
for checking parameterized answers.)

\solution{
}
\end{problemparts}
\end{problem}           

                                 