\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}