%Used to come before Trees: proof read for switched references

\hyperdef{graph}{coloring}{\section{Coloring Graphs}}
In section~\ref{sexam},
\iffalse
\href{http://courses.csail.mit.edu/6.042/fall07/ln5-6.pdf#sex.america}{``Sex
in America''} graph in Week 5-6 Notes
\fi
we used edges to indicate an affinity between two nodes, but having an
edge represent a \emph{conflict} between two nodes also turns out to be
really useful.  For example, each term the MIT Schedules Office must
assign a time slot for each final exam.  This is not easy, because some
students are taking several classes with finals, and a student can take
only one test during a particular time slot.  The Schedules Office wants
to avoid all conflicts.  Of course, you can make such a schedule by having
every exam in a different slot, but then you would need hundreds of slots
for the hundreds of courses, and exam period would run all year!  So, the
Schedules Office would also like to keep exam period short.

The Schedules Office's problem is easy to describe as a graph.  There
will be a vertex for each course with a final exam, and two vertices will
be adjacent exactly when some student is taking both courses.  For
example, suppose we need to schedule exams for 6.041, 6.042, 6.002, 6.003
and 6.170.  The scheduling graph might look like this:

\mfigure{!}{1.5in}{figures/finals-subject-labels.pdf}

6.002 and 6.042 cannot have an exam at the same time since there are
students in both courses, so there is an edge between their nodes.  On the
other hand, 6.042 and 6.170 can have an exam at the same time if they're
taught at the same time (which they sometimes are), since no student can
be enrolled in both (that is, no student \emph{should} be enrolled in both
when they have a timing conflict).  Next, identify each time slot with a
color.  For example, Monday morning is red, Monday afternoon is blue,
Tuesday morning is green, etc.

Assigning an exam to a time slot is now equivalent to coloring the
corresponding vertex.  The main constraint is that \emph{adjacent vertices
  must get different colors} ---otherwise, some student has two exams at
the same time.  Furthermore, in order to keep the exam period short, we
should try to color all the vertices using as \emph{few different colors
  as possible}.  For our example graph, three colors suffice:

\mfigure{!}{1.5in}{figures/finals-colored.pdf}

This coloring corresponds to giving one final on Monday morning (red),
two Monday afternoon (blue), and two Tuesday morning (green).

Can we use fewer than three colors?  No! We can't use only two colors
since there is a triangle in the graph, and three vertices in a triangle
must all have different colors.

This is an example of what is a called a \emph{graph coloring problem}:
given a graph $G$, assign colors to each node such that adjacent nodes
have different colors.  A color assignment with this property is called a
\emph{valid coloring} of the graph ---a ``coloring,'' for short.  A graph
$G$ is \term{$k$-colorable} if it has a coloring that uses at most $k$
colors.  The minimum value of $k$ for which a coloring exists is called
the \term{chromatic number}, $\chi(G)$, of $G$.

In general, trying to figure out if you can color a graph with a fixed
number of colors can take a long time.  It's a classic example of a
problem for which no fast algorithms are known.  In fact, it is easy to
check if a coloring works, but it seems really hard to find it (if you
figure out how, then you can get a \$1 million Clay prize).

\subsection{Degree-bounded Coloring}

There are some simple graph properties that give useful upper bounds on
colorings.  For example, if we have a bound on the degrees of all the
vertices in a graph, then we can easily find a coloring with only one more
color than the degree bound.

\begin{theorem}\label{k+1-colorable}
A graph with maximum degree at most $k$ is $(k+1)$-colorable.
\end{theorem}

Unfortunately, if you try induction on $k$, it will lead to disaster.  It
is not that it is impossible, just that it is extremely painful and would
ruin you if you tried it on an exam.  Another option, especially with
graphs, is to change what you are inducting on.  In graphs, some good
choices are $n$, the number of nodes, or $e$, the number of edges.

\begin{proof}
We use induction on the number of vertices in the graph, which we
denote by $n$.  Let $P(n)$ be the proposition that an $n$-vertex graph
with maximum degree at most $k$ is $(k+1)$-colorable.

\textbf{Base case}: ($n=1$) A 1-vertex graph has maximum degree 0 and is
1-colorable, so $P(1)$ is true.

\textbf{Inductive step}: Now assume that $P(n)$ is true, and let $G$ be an
$(n+1)$-vertex graph with maximum degree at most $k$.  Remove a vertex $v$
(and all edges incident to it), leaving an $n$-vertex subgraph, $H$.  The
maximum degree of $H$ is at most $k$, and so $H$ is $(k+1)$-colorable by
our assumption $P(n)$.  Now add back vertex $v$.  We can assign $v$ a
color different from all its adjacent vertices, since there are at
most $k$ adjacent vertices and $k+1$ colors are available.  Therefore, $G$
is $(k+1)$-colorable.  This completes the Inductive step, and the theorem
follows by induction.
\end{proof}


Sometimes $k+1$ colors is the best you can do.  For example, in the
complete graph, $K_{n}$, every one of its $n$ vertices is adjacent to all
the others, so all $n$ must be assigned different colors.  Of course $n$
colors is also enough, so $\chi(K_n)=n$.  So $K_{k+1}$ is an example where
Theorem~\ref{k+1-colorable} gives the best possible bound.  This means
that Theorem~\ref{k+1-colorable} also gives the best possible bound for
\emph{any} graph with degree bounded by $k$ that has $K_{k+1}$ as a
subgraph.

\iffalse
obviously requires $k+1$ 
Consider a graph on $n$
nodes with all possible edges, so $d=n-1$.  This is called the {\em
complete graph} $K_n$ or a {\em clique}, just like a clique of friends,
where nodes represent the people and an edge represents the friendship
relationship.\footnote{ When speaking of friends, clique is usually
pronounced similar to click.  However, for some reason, graph theorists
think that the word clique rhymes with geek.}

\mfigure{!}{1.5in}{figures/complete-graph.pdf}
\fi

But sometimes $k+1$ colors is far from the best that you can do.  Here's
an example of an $n$-node star graph for $n=7$:

\mfigure{!}{1.5in}{figures/star-graph.pdf}

In the $n$-node star graph, the maximum degree is $n-1$, but the star only
needs $2$ colors!


\subsection{Why coloring?}

Coloring problems come up in all sorts of applications.  For example, at
Akamai, a new version of software is deployed over each of 20,000 servers
every few days.  The updates cannot be done at the same time since the
servers need to be taken down in order to deploy the software.  Also, the
servers cannot be handled one at a time, since it would take forever to
update them all (each one takes about an hour).  Moreover, certain pairs
of servers cannot be taken down at the same time since they have common
critical functions.  This problem was eventually solved by making a 20,000
node conflict graph and coloring it with 8 colors -- so only 8 waves of
install are needed!

Another example comes from the need to assign frequencies to radio
stations.  If two stations have an overlap in their broadcast area, they
can't be given the same frequency.  Frequencies are precious and
expensive, so you want to minimize the number handed out.  This amounts to
finding the minimum coloring for a graph whose vertices are the stations
and whose edges are between stations with overlapping areas.

Coloring also comes up allocating registers for program variables.  While
a variable is in use, its value needs to be saved in a register, but
registers can often be reused for different variables.  But two variables
need different registers if they are referenced during overlapping
intervals of program execution.  So register allocation is the coloring
problem for a graph whose vertices are the variables; vertices are
adjacent if their intervals overlap, and the colors are registers.

Finally, there's the famous
\href{http://courses.csail.mit.edu/6.042/spring09/ln1.pdf#map.color}{map
  coloring problem} mentioned in Week 1 Notes.  The question is how many
colors are needed to color a map so that adjacent territories get
different colors?  This is the same as the number of colors needed to
color a graph that can be drawn in the plane without edges crossing.  A
proof that four colors are enough for the \emph{planar} graphs was
acclaimed when it was discovered about thirty years ago.  Implicit in that
proof was a 4-coloring procedure that takes time proportional to the
number of vertices in the graph (countries in the map).  On the other
hand, it's another of those million dollar prize questions to find an
efficient procedure to tell if a planar graph really \emph{needs} four
colors or if three will actually do the job.  But it's always easy to tell
if an \emph{arbitrary} graph is 2-colorable, as we show in
Section~\ref{bipartitesec}.  Then in Section~\ref{planarsec}, we'll
develop enough planar graph theory to present an easy proof that planar
graphs are 5-colorable.

\endinput