\documentclass[10pt]{article}
\include{18313-preamble}
\usepackage{graphicx}

\begin{document}
\lecture{2004/04/30}{Dan Ports}{2004/05/03}{drkp@mit.edu}
\lecturetitle{A List Analogue of Equitable Coloring}{A. V. Kostochka,
  M. J. Pelsmajer, and D. B. West. J. Graph Th. 44-3, Nov. 2003}{Dan
  Ports}{Dan Ports}

\section{Preliminaries}
\label{sec:preliminaries}

This paper concerns \emph{list coloring}. A \emph{list assignment} is
a set $L(v)$ of allowable colors for every vertex $v$ in a graph. In
particular, a \emph{$k$-uniform} list assignment is a list assignment
$L$ for a graph $G$ satisfying $\abs{L(v)} = k$ for all $v \in V(G)$.
For a list assignment $L$, a \emph{$L$-coloring} is a \emph{proper
  vertex coloring} --- an assignment of colors to vertices such that
no edge connects two vertices of the same color --- in which the
colors for each vertex $v$ are chosen from the corresponding list
$L(v)$.  A graph $G$ is \emph{equitably $L$-colorable} if a
$L$-coloring of $G$ exists such that each color appears at at most
$\left\lceil\frac{n}{k}\right\rceil$ vertices.  Moreover, a graph $G$
is \emph{equitably $K$-choosable} if it is equitably $L$-colorable for
all $k$-uniform list assignments $L$. This captures the notion that
all colorings can be made ``equitably'', balanced between each color.


\section{The main result, and proof thereof}
\label{sec:main-result}
The theorem of this paper shows that most suitably small graphs (not
too many vertices or too high degree) are $k$-choosable unless they
contain a complete graph:
\begin{theorem}
  \label{thm:1}
  If $G$ is a graph and $k \ge \max\{\Delta(G), \frac{n(G)}{2}\}$,
  then $G$ is equitably $k$-choosable unless $G$ contains $K_{k+1}$,
  or $G$ is $K_{k,k}$ with $k$ odd.
\end{theorem}
\begin{proof}
  The proof is by contradiction. Consider a minimal counterexample G
  that has the fewest vertices. Let $L$ be a $k$-uniform list
  assignment in which some color is used at least three times in every
  $L$-coloring of $G$. Then choose $y \in G$ and a $f$ a 2-bounded
  $L$-coloring of $G-y$ that maximizes the number of color classes
  with two vertices in $f$ (we know one exists because $G$ is
  minimal).
  
  Define $$U = \{f(v) | v \in V(G) - \{y\}\}$$
  i.e. the colors used in
  $f$ and and $U_i$ to be the set of colors used $i$ times by $f$ ($i
  = 1$ or $2$). Also define the neighbors of $v$,
  $$N(v) = \{u: uv \in E(G)\}$$
  and
  $$N[v] = N(v) \cup \{v\}$$
  Counting the number of times each color
  is used, and since $n \le 2k$,
  \begin{equation}
    \label{eq:1}
    2\abs{U_2} + \abs{U_1} < 2k
  \end{equation}
  
  We now introduce the notion of \emph{switching}. For $x \neq y$, we
  assign $x$'s color $f(x)$ to $y$ and make $x$ uncolored; this
  creates a new graph $G-x$ that is the analog of $G-y$ with $x$ and
  $y$'s roles reversed. We say that $x$ is \emph{switchable} if
  switching on $x$ gives a 2-bounded L-coloring of $G-x$.
  
  Define \[Z = \{x \in V(G) | f(x) \in U_1 \cap L(y)\}\] Every vertex
  in $Z$ is switchable, since the color is available in $L(y)$ and
  there are no other vertices with the same color to conflict with it.

  \begin{claim}
    \label{cl:1}
    If a vertex $x$ is switchable, then $L(x) \subseteq U$. Also,
    $L(y) \subseteq U$. Furthermore, $Z \subseteq N(y)$.
  \end{claim}

  \begin{proof}
    By contradiction: first, if $L(x)$ contained colors not in $U$,
    then these colors are not used; we could switch on $x$ and then
    color $x$ with one of the unused colors, contradicting that $G$
    has no 2-bounded $L$-coloring. Similarly, if $L(y) \not \subseteq
    U$, then we could use the unused color to color $y$ and create a
    2-bounded $L$-coloring of $G$. Second, if $z \in Z$ is not
    adjacent to $y$, we could assign $f(z)$ to $y$ without a conflict,
    and create a 2-bounded $L$-coloring of $G$.
  \end{proof}

  \begin{claim}
    \label{cl:2}
    If $u$ and $v$ are vertices such that $u$ is switchable and $v \in
    Z$ (and hence $v$ is also switchable), then $uv \in E(G)$. In
    particular, $Z \subseteq N[u]$.
  \end{claim}

  \begin{proof}
    Again, by contradiction: suppose $uv \notin E(G)$. We consider two
    cases:
    \begin{enumerate}
    \item Suppose there exists a $c$ in $L(u) \cap L(v) \cap U_1$. Let
      $z \in V(G)$ be the vertex having color $c$. We first dispense
      with the cases $z = u$ or $z = v$: in these cases we can switch
      on $z$ and give color $c$ to $z$, creating a 2-bounded
      $L$-coloring of $G$.
    
      Otherwise, we can uncolor $z$, switch on $u$, and color $u$ and
      $v$ color $c$. The result of this sequence of operations is that
      $z$ is the uncolored vertex (``y''), and $u$ and $v$ have the
      same color, whereas they had different colors before. This means
      that the resulting 2-bounded $L$-coloring of $G$ has more color
      classes that contain two vertices than $f$ does, which
      contradicts our choice of $f$.
    \item Otherwise, $L(u) \cap L(v) \cap U_1 = \emptyset$. By
      Claim~\ref{cl:1}, $L(u) \cup L(v) \subseteq U$, and so $L(u)
      \cap L(v) \subseteq U_2$, since $U = U_1 \cup U_2$. Since $L$ is
      a $k$-uniform list assignment, we perform some elementary set
      size operations and find
      \[ 2k = \abs{L(u)} + \abs{L(v)} = \abs{L(u) \cup L(v)} +
      \abs{L(u) \cap L(v)} \le \abs{U_1 \cup U_2} + \abs{U_2} \] This
      contradicts (\ref{eq:1}), proving the claim. \qedhere
    \end{enumerate}
  \end{proof}
  
  Define:
  \[Z' = \{x \in V(G) | f(x) \in U_2 \cap L(y)\}\]

  \begin{claim}
    \label{cl:3}
    $Z$ is non-empty. If $z \in Z$, then $d(z) = k$, and $x \in N(z) -
    \{y\}$ if and only if $x$ is switchable. Also, $d(y) = k$ and
    $f(N(y)) \subseteq L(y)$, and $\abs{N(y) \cap Z'} =
    \frac{\abs{Z'}}{2}$.
  \end{claim}

  \begin{proof}
    Since $L(y) \subseteq U$, % FIXME: huh?
    \[ 2(k-\abs{Z}) = \abs{Z'} \le n(G) - 1 \le 2k- 1\] So $Z$ is
    non-empty. We can choose some vertex $z \in Z$.
    
    Note that a vertex of $Z'$ can be switched with $y$ precisely if
    and only if the other vertex having the same color is not a
    neighbor of $y$. So the number of non-switchable vertices in $Z'$
    is the number of neighbors of $y$ in $Z'$ (call this number $s$).
    Claim~\ref{cl:2} tells us that since $z$ is in $Z$, it is adjacent
    to all switchable vertices: all of $Z'$, and $Z - \{z\}$. So we
    obtain the bound
    \[d(z) \ge \abs{Z'} - s + \abs{Z} = 2k - s - \abs{Z}\]
    We use the fact that $\Delta(G) \le k$ to obtain
    \begin{align*}
      k &\ge d(z) \ge 2k-s-\abs{Z}\\
      \abs{Z} + s &\ge k\\
    \end{align*}
    which forces the bound $k \ge d(y) \ge \abs{Z} + s$ to the simple
    equality $d(y) = k = \abs{Z} + s$, and so $d(z) = k$. Therefore,
    $y$ is the only non-switchable neighbor of $z$. And $N(y)
    \subseteq Z \cup Z'$, so $f(N(y)) \subset L(y)$. Finally, we note
    that
    \[\abs{Z'} = 2(k - \abs{Z}) = 2s\]
    so, since $s$ is the number of vertices in $Z'$ adjacent to $y$,
    exactly half the vertices in $Z'$ are adjacent to $y$.
  \end{proof}
  
  We say that a color class in $Z'$ is of \emph{type $i$} if it
  contains $i$ vertices that are switchable. Note that $i$ is
  therefore also the number of vertices of that color outside $N(y)$.
  By Claim~\ref{cl:3}, exactly half of $Z'$ is in $N(y)$. So the
  number of type 2 color classes is equal to the number of type 1
  color classes.
  
  Note that switching does not change the size of any color class: one
  vertex is made uncolored, and the previously uncolored vertex $y$ is
  colored with that color. So the previous three claims can be applied
  to the new coloring produced by the switch.

  \begin{claim}
    \label{cl:4}
    If $x$ is a switchable vertex of $Z'$, then $d(x) = k$ and $f(N(x)
    - \{y\}) \subseteq L(x)$, and $N[x]$ contains all switchable
    vertices in $Z' \cap N(y)$.
  \end{claim}

  \begin{proof}
    The vertex $x$ is switchable, so we switch on it. This produces a
    new coloring $f'$ on $G-x$, in which x is the ``new $y$''.
    Therefore, by Claim~\ref{cl:3}, $d(x) = k$. Moreover, $x$'s
    neighbors have not changed, so by Claim~\ref{cl:3} $f(N(x) -
    \{y\}) \subseteq L(x)$.
    
    Now let $x'$ be another switchable vertex in $Z' \cap N(y)$ ($x'
    \neq x$), and $z \in Z$. Both $x$ and $x'$ are switchable, so they
    are neighbors of $z$. The other vertex with color $f(x')$ cannot
    be a neighbor of $z$. Now switch on $x$ to give a coloring $f'$ of
    $G-x$. We know $f'(z) \in L(x)$ since $z \in N(x)$, and so we can
    consider $z$ a vertex in the analogous set to $Z$ in the new
    coloring. Applying Claim~\ref{cl:3} to the new coloring, z is
    adjacent to $x'$ but not to the other vertex of the same color, so
    $f(x')$ is a type 1 color class. Therefore, $x'$ is switchable
    with respect to $f'$, since it is the only vertex of its color
    adjacent to $x$ (the ``new $y$''). So $x' \in N(x)$.
    %FIXME: penultimate sentence isn't quite right.
  \end{proof}
  
  We now return to Theorem~\ref{thm:1}, and consider the three cases
  that result from the possible composition of $Z'$'s color classes:

  \begin{enumerate}
  \item $Z'$ contains only type-1 color classes. Since all switchable
    vertices in $Z$ are neighbors of $y$, this means $N(y)$ contains
    all switchable vertices. And $N(y)$ contains no other vertices.
    The degree of $y$ is $k$, so there must be $k$ switchable vertices
    in $N(y)$. Claim~\ref{cl:4} tells us that all of these switchable
    vertices, and $y$, are neighbors of each other, i.e. they are
    isomorphic to the complete graph $K_{k+1}$.
    
  \item $Z'$ contains both type-1 and type-2 color classes. Choose a
    color class of type 1 and call it $\{x, x'\}$, where $x$ is the
    vertex that is a neighbor of $y$. Choose a color class of type 2
    and call it $\{w, w'\}$. Choose $z \in Z$. Thus, by
    Claim~\ref{cl:3}, $x, w, w' \in N(z)$, and $x' \notin N(z)$. We
    first switch on $x$. By Claim~\ref{cl:4}, $z$ will be a vertex of
    the ``new $Z$'' in the new coloring $f_x$. Since $w$ and $w'$ are
    still neighbors of $z$, they are both switchable under $f_x$ (by
    Claim~\ref{cl:3}) and by definition this is a type-2 color class.
    This means $w$ and $w'$ are cannot be neighbors of $x$.
    
    We next switch on $w$. Again, $z$ will be a vertex of the ``new
    $Z$'' under the new coloring $f_w$. But by Claim~\ref{cl:3}, $x$
    is switchable under $f_w$ and $x'$ is not because $x$ is adjacent
    to $z$ and $x'$ is not. This means that $\{x, x'\}$ is a type-1
    color class, with $x \in N(w)$. We now have a contradiction: $w
    \notin N(x)$ but $x \in N(w)$.
    
  \item $Z'$ contains no color classes of type 1. Suppose first that
    $Z'$ contains no color classes at all, i.e. $Z' = \emptyset$. Then
    $Z$ has $k$ elements, and they are all connected to each other and
    to $y$, so $Z \cup \{y\}$ is isomorphic to $K_{k+1}$, as in the
    first case.
    
    Otherwise, $Z'$ has at least one type 2 class; choose one and call
    it $\{x, x'\}$. We claim that $Z$ has exactly one vertex. We know
    by Claim~\ref{cl:3} that it has at least one. Suppose it has two,
    $z$ and $z'$. Then the neighbors of $z$ and $z'$ are the same, and
    both contain $x$ and $x'$.  If we switch about $z'$, the new
    coloring $f'$ has both $y$ and $z$ in the ``new $Z$'' since $z$
    and $z'$ were in $Z$ in the old coloring. By Claim~\ref{cl:3}, $y$
    and $z$ must be adjacent to the same set of all switchable
    vertices, i.e. $N[y] = N[z]$. But we showed earlier that $x$ and
    $x'$ were in $N[z]$, and $x$ and $x'$ are not in $N[y]$ by
    definition since they are a type-2 class. Thus $N[y] \neq N[z]$.
    This is a contradiction, so $Z$ contains exactly one vertex. Call
    it $z$.
    
    Define $X$ to be the vertices in color classes of type 0 in $Z'$,
    as well as the vertex $z$. Define $Y$ as the set of vertices in
    type-2 color classes in $Z'$, and the vertex $y$. We will show
    that $G$ contains no vertices that are not in the union of $X$ and
    $Y$. By Claim~\ref{cl:3}, $f(N(y)) \subseteq L(y)$. So by
    definition of $Z$ and $Z'$, $N(y) \subseteq Z \cup Z'$.
    Claim~\ref{cl:2} asserts that the degree of $y$ is $k$, and we
    concluded that $\abs{Z} = 1$, so $N(y)$ must consist of the one
    element in $Z$ and $k-1$ elements in $Z'$. By the definitions of
    each class type, the number of vertices in the type 0 classes of
    $Z'$ is $N(Y) \cap Z' = k -1$, and this is the necessarily the
    same as the number of vertices in type 2 classes.  So $X$ contains
    $z$ and the $k-1$ type-0 class vertices, and $Y$ contains $y$ and
    the $k-1$ type-2 class vertices; both $X$ and $Y$ contain $k$
    elements. Therefore $\abs{X \cup Y} = 2k$. And we are assuming
    that $G$ contains no more than $2k$ vertices, so all vertices in
    $G$ must be in $X \cup Y$.
    
    Moreover, $k$ must be odd, since the elements of $Z'$ come in
    pairs (they are all of colors that have two vertices associated
    with them), and there is the lone vertex $z$.
    
    We now show that $G$ must be the complete bipartite graph
    $K_{k,k}$, where $X$ and $Y$ are the partite sets. Note that the
    neighbors of $z$ are $Y$: the vertex $y$ and the $k-1$ switchable
    vertices $N(z)-\{y\}$ are in $Y$. For each $w \in Y - \{y\}$,
    switch on $w$ and call the resulting coloring $f'$. In each
    coloring, $z$ is still the only vertex in the ``new $Z$'' and $w$
    is the ``new $y$''. The type 0 classes are still $X - \{z\}$, so
    $X \subseteq N(w)$, and $X = N(w)$ since $d(w) = k = \abs{X}$.
    Thus every vertex in $X$ is connected to every vertex in $Y$, i.e.
    $G$ is the bipartite graph $K_{k,k}$ since $\Delta(G) \le k$.
  \end{enumerate}
  
  We now step back and observe the results of our proof by
  contradiction. Assuming a minimal counterexample $G$, we reached
  three cases. In the first case, $G$ contained $K_{k+1}$. In the
  second case, we reached a contradiction. In the third case, $G$
  either contained $K_{k+1}$ or $K_{k,k}$ with $k$ odd in the latter
  case. By contradiction, therefore, we have proven
  Theorem~\ref{thm:1}: every graph $G$ satisfying $k \ge
  \max\{\Delta(G), \frac{n(G)}{2}\}$, is equitably $k$-choosable
  unless it contains $K_{k+1}$, or it is $K_{k,k}$ with $k$ odd.
\end{proof}

\end{document}