\documentstyle{article}
\textheight=160mm
\textwidth=105mm
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newenvironment{pf}{\par\medskip\noindent{\bf
Proof}}{$\Box$\par\medskip}
\def\e{\mbox{{\rm e}}}
\sloppy
\hyphenation{Haj-nal}
\def \nl {\newline}
\def \ssk {\smallskip}
\def \msk {\medskip}
\def \bsk {\bigskip}
\def \ni  {\noindent}
\def \nin {\bsk\ni}
\def \ssp {\vspace{2mm}}    % small vertical space
\def \psp {\msk\ni}         % paragraph space

\def \pf  {{\ni \bf Proof. }}
\def \eb  {\hfill $\Box$}   % end of proof

\def \smin {\setminus}
\def \es   {\emptyset}
\def \sst  {\subset}
\def \ssq  {\subseteq}
\def \vp   {\varphi}


\title{Brooks-type theorems for choosability with separation}
\author{J. Kratochv\'{\i}l\thanks{Department of Applied Mathematics,
Charles University, Malostransk\'e n\'am. 25, 118 00 Prague, Czech Republic. 
E-mail:
{\tt honza@kam.ms.mff.cuni.cz}. This author acknowledges partial support of
Czech research grants GA\v CR 0194 and GAUK 194/1996.}
 \and Zs.\ Tuza\thanks{Computer and Automation Institute,
Hungarian Academy of Sciences, H--1111 Budapest, Kende u.\ 13--17,
Hungary. E-mail: {\tt tuza@lutra.sztaki.hu}. Research supported in
part by the National Scientific Research Fund, grants OTKA 7558 and
T-016416.}
 \and M. Voigt\thanks{Institut f\"ur Mathematik,
 Technische Universit\"at Ilmenau, D--98684 Ilmenau, Germany. E-mail: {\tt voigt@mathematik.tu-ilmenau.de}.}}
%\date{\scriptsize This copy was printed on November 8, 1996. }


\begin{document}

\maketitle

\begin{abstract}
We consider the following type of problems.
  Given a graph $G=(V,E)$ and lists
$L(v)$ of allowed colors for its vertices $v \in V$
such that $|L(v)|=p$ for all $v \in V$ and  $|L(u) \cap L(v)| \leq c$ for all 
$uv \in E$, is it possible to find a ``list coloring", i.e.,
a color $f(v)\in L(v)$ for each $v\in V$,
so that $f(u) \not= f(v)$ for all $uv \in E$\,? We prove that every graph of
maximum degree $\Delta$ admits  a  list coloring for every such  list 
assignment, provided $p\ge \sqrt{5.437c\Delta}$. Apart from a multiplicative
constant, the result is tight, as lists of length $\sqrt{0.5c\Delta}$
may be necessary. Moreover, for $G=K_n$ (the complete graph on $n$ vertices)
and $c=1$ (i.e., almost disjoint lists), the smallest value of $p$ is shown to
have asymptotics $(1+o(1))\sqrt{n}$. For planar
graphs and $c=1$, lists of length 4 suffice.
\end{abstract}


\section{Introduction}

Let $p, q, r$ be natural numbers, and $G=(V,E)$ a graph with vertex set $V$
and edge set $E$. A {\em $(p,r)$-assignment} of $G$ is a collection
$ {\cal L} = \{ L(v)~ |~ v  \in V \} $ of lists (sets) of ``colors"
 assigned to the vertices
such that

$ |L(v)| = p $ for all $v \in V$, and

$|L(u) \cup L(v) | \geq p + r$ for all $uv \in E$.\\
An {\em $\cal L$-admissible q-set coloring} of $G$ is a collection
${\cal F} = \{ F(v)~ |~ v \in V \} $ such that

$ F(v) \ssq L(v)$ for all $v \in V$,

$ |F(v)| = q $ for all $v \in V$, and

$|F(u) \cap F(v)| = \es$ for all $uv \in E$.\\
The graph $G$ is said to be {\em (p,q,r)-choosable} if it admits a $q$-set
coloring for every $(p,r)$-assignment $\cal L$.


This concept was introduced in \cite{KTV}, where mainly the computational
complexity issues were considered.

One can easily see by induction on the number of vertices 
that every graph of maximum degree $\Delta$
is  $(\Delta m +m, m, 0)$-choosable
for every natural number $m$.
What is more, extending a Brooks-type theorem of Erd\H os, Rubin and
Taylor \cite{ERT}, it has been proved in \cite{ZsM} that if each
connected component in a graph of maximum degree $\Delta$ contains a
block (maximal 2-connected subgraph) different from complete graphs
and odd cycles, then the graph is $(\Delta m, m,0)$-choosable.
(As a matter of fact, for each vertex, a list of length $m$ times the
vertex degree suffices.)

In the present paper our goal is to show that restrictions on the
intersections of lists of adjacent vertices  lead to stronger sufficient conditions for the
existence of list colorings.
E.g., it is now well known that planar
graphs are 5-choosable~\cite{Th} but not always 4-choosable~\cite{ma}.
One of our results shows that every planar graph is
$(4,1,3)$-choosable, i.e., if the 4-element lists assigned
to adjacent vertices have  at most one color in common, one can always
find an admissible coloring.                                                 
%! one of two "always" deletet
%We have shown in a separate paper
%that every planar graph is $(4,1,2)$-choosable, i.e., if the 4-lists assigned
%to adjacent vertices have always at most two colors in common, one can
%always find a feasible coloring.

%In the present paper we attend to the degrees of vertices.
We first consider complete graphs. In general, the complete graph
on $n$ vertices has choosability $n$. A simple observation shows that
$K_n$ is $(n-2,1,1)$-choosable, i.e., requiring that adjacent
vertices are assigned distinct lists guarantees the existence of a feasible
coloring even if the lists are smaller than the choosability by 2. Requiring
that adjacent lists have small intersections affects the choosability even
more drastically. Our Theorem~\ref{zscom1} shows that $K_n$ is
$(\lfloor\sqrt{n}\rfloor+2,1,\lfloor\sqrt{n}\rfloor+1)$-choosable, 
and we also prove that this bound is assymptotically  best possible.
In Section~\ref{brsc} we consider a variant of Brooks's theorem: we show
that  a graph of maximum degree $\Delta$ is $(\lceil\sqrt{5.437(\Delta-1)}\rceil,1,
\lceil\sqrt{5.437(\Delta-1)}\rceil-1)$-choosable.
(Up
to a multiplicative constant, this result is also tight due to the bounds
for complete graphs  established in Section~\ref{com}.) The proof
of this result is 
nonconstructive, and we prove a constructive (but generally weaker) 
estimate in the last
section.

 
In order to simplify the formulation of our results, we introduce the following
notation.
For a graph $G$ and a nonnegative integer $c$, we denote by 
$\zeta(G,c)$  the minimum integer $k$ such that
$G$ is $(k,1,k-c)$-choosable. Note that $G$ is then $(k,1,k-c)$-choosable
for every $k\ge \zeta(G,c)$ (deleting arbitrary $k-\zeta(G,c)$ colors from every
list in a given $k$-assignment we obtain an instance of
$(\zeta(G,c),1,\zeta(G,c)-c)$-list coloring, which is by definition always 
%! 1 replaced by c
feasible).
% and that $\zeta(G,c)\le ch(G)$.

\section{Complete graphs}\label{com}

We  consider complete graphs in this section. First we mention the case
where the lists assigned to distinct vertices are mutually distinct.

\begin{prop}\label{triv}
For $n\ge 3$, the complete graph $K_n$ is $(k,1,1)$-choosable if and only
if $k=1$ or $k\ge n-2$.
\end{prop}

\begin{pf}
The case $k=1$ is trivial, a $(1,1)$-assignment is itself a proper coloring.

Suppose $k\ge n-2$ and suppose the lists $L(u),u\in V(K_n)$ are distinct.
Note that for a complete graph, a list coloring is just a system of disinct
representatives of the lists. We show that 
$$|\bigcup_{u\in X}L(u)|\ge|X|$$
for every $X\subset V(K_n)$. This is obvious for $|X|\le n-2$. For $|X|=n-1
\ge 2$, $|\bigcup_{u\in X}L(u)|\ge k+1\ge n-1=|X|$. Finally,
since an $(n-1)$-element
set has only $n-1$ distinct $(n-2)$-element subsets, $|\bigcup_{u\in X}L(u)|\ge
n$ for $|X|=n$. Thus, the existence of an $\cal L$-admissible coloring 
follows by Hall's theorem.

For $2\le k\le n-3$, we have ${n-1\choose k}\ge n$ and one can find $n$
distinct $k$-element subsets of an $(n-1)$-element color set. Assigning these
subsets to  the vertices of $K_n$ we obtain a non-feasible $(k,1)$-assignment,
since the total number of colors is less than the number of vertices.
\end{pf}

In the sequel, we deal with the case where the lists assigned to adjacent 
vertices
differ substantially. In particular, a $(k,k-c)$-assignment is such that the
intersections of lists assigned to adjacent vertices have size at most $c$.
Recall the definition of $\zeta(G,c)$ from the previous section. We consider
$c=1$ first.

\begin{thm}\label{zscom1}
Let $n\ge3$. 
 Then $\zeta(K_n,1)\le \lfloor\sqrt{n-{11 \over
4}}+{3\over 2}\rfloor$.
\end{thm}

\begin{pf}
Let $k_0 = \lfloor\sqrt{n-{11 \over
4}}+{3\over 2}\rfloor$, i.e., $k_0$ is the smallest integer greater than $\sqrt{n-{11 \over
4}}+{1\over 2}$.
Suppose we are given $n$ color sets $L_1,L_2,\ldots,L_n$
of size $k_0$ each, such that the
intersection of any two of them has at most one element. As in the previous
proof, a feasible
coloring of this $K_n$ is then a system of distinct representatives for the
$L_i$'s. We will show its existence via Hall's theorem. Let
$X$ be a subset of $\{1,2,\ldots,n\}$, say $|X|=t$. We need to show that
$|\bigcup_{i\in X}L_i|\ge t$. Suppose on the contrary that
$|\bigcup_{i\in X}L_i|\le t-1$. Consider the
at most $t-1\choose 2$                                                    
%!  "at most" added
pairs of colors from
$\bigcup_{i\in X}L_i$. Since the color sets are almost disjoint, each of
these pairs belongs to at most one $L_i$. Hence
$$t{k_0\choose 2}\le{t-1\choose 2},$$
which yields
$$tk_0(k_0-1)\le(t-1)(t-2),$$
$$k_0(k_0-1)\le \lfloor{{(t-1)(t-2)\over t}}\rfloor=
\lfloor t-3+{{2\over t}}\rfloor
\le\lfloor n-3+{{2\over n}}\rfloor=n-3.$$
It follows that
$$k_0^2-k_0-(n-3)\le 0$$
and hence
$$k_0\le{{1+\sqrt{4n-11}\over 2}}<k_0$$
a contradiction.
\end{pf}

The following theorem shows that the bound given in
Theorem~\ref{zscom1} is the best possible 
for infinitely many values of $n$:

\begin{thm}        \label{zscom2}
For any prime power $q$, $\zeta(K_{q^2+1},1)=q+1$.
\end{thm}

\begin{pf}
Take an affine plane of order $q$. It has $q+1$
classes of parallel lines, $q$ lines per class, $q$ points per line.
Any two nonparallel lines share exactly one  point. Forget
arbitrary $q-1$ of the lines and view the remaining $q^2+1$ lines as
color sets (the points of the plane are viewed as colors). In this
assignment any two lists share at most one color, and the assignment
does not allow an admissible coloring, since the total number $q^2$ of colors
 is less than the number ($q^2+1$) of sets.
\end{pf}

Theorem~\ref{zscom1} also gives the correct  asymptotics  for
$\zeta(K_n,1)$:

\begin{thm}        \label{zscom3}
We have \quad $lim_{n\rightarrow \infty}{\zeta(K_n,1)\over\sqrt{n}}=1$.
\end{thm}

\begin{pf}
The proof  is again based on finite planes. Given an $n$
(which is supposed to be large enough), let $q$ be the smallest prime such that
$q^2\ge n$. It is well known that for any real $\varepsilon$ and
any natural number $n$ sufficiently large with respect to $\varepsilon$,
there is a prime between $n$ and $(1+\varepsilon)n$.
Therefore $q^2-n=o(n)$ and $q=\sqrt{n}+o(\sqrt{n})$. Take an affine plane
of order $q$, choose a class of parallel lines and remove 
$\lceil{{q^2-n+1}\over{q}}\rceil=o(q)$ of them together with all points of these
lines. Consider the remaining $q^2$ (shortened) lines as color sets.
We have $q^2\ge n$ color sets, any two of them share at most one color, and
they have equal size $s=q-\lceil{{q^2-n+1}\over{q}}\rceil=q-o(q)$. Their union
has $q^2-q\lceil{{q^2-n+1}\over{q}}\rceil\le q^2-q^2+n-1=n-1$ colors, and
therefore it is impossible to choose distinct colors from the sets. This
shows that $\zeta(K_n,1)>s=q-o(q)=\sqrt{n}-o(\sqrt{n})$,                   
%! c replaced by 1
and so the statement follows from Theorem~\ref{zscom1}.
\end{pf}

For the case of $c>1$,  a lower bound on $\zeta(K_n,c)$
is given by the following result.



\begin{thm}\label{kvadrat}
For every integer $c\ge 2$,
$$\liminf_{n\rightarrow\infty}\frac{\zeta(K_n,c)}{\sqrt{n}}\ge
\sqrt{\lfloor\frac{c}{2}\rfloor}.$$
\end{thm}

\begin{pf}
Suppose $n$ is large enough (compared to $c$) and let $q$ be the largest
prime such that $q^2\lfloor\frac{c}{2}\rfloor<n$. Again,
$\sqrt{\frac{n}{\lfloor\frac{c}{2}\rfloor}}-q=o(\sqrt{n})$ and
$q>\sqrt{\frac{n}{2\lfloor\frac{c}{2}\rfloor}}$. For $n$ large
enough, $q>c$. We consider the
point set $M=\{0,1,\ldots,q\lfloor\frac{c}{2}\rfloor-1\}\times GF(q)$. For
any quadratic function $f$ on $GF(q)$, let $M_{f}=
\{(x,f(x\mbox{ mod }q)):0\le x\le q\lfloor\frac{c}{2}\rfloor-1\}$, i.e.,  
%! ) added
$M_f$ consists of the graph of the function $f$ and its translates.
Let $\cal F$ be a set of $n$ distinct quadratic functions over $GF(q)$.
Since the total number of quadratic functions is
$q^3>c\frac{n}{2\lfloor\frac{c}{2}\rfloor}\ge n$, we can find such $\cal
F$. We set $M({\cal F})=\{M_f:f\in{\cal F}\}$.

Given a complete graph with $n$ vertices, we associate its vertices with
the functions in $\cal F$ and view the sets $M_f, f\in{\cal F}$ as lists
assigned to the vertices. The size of each list is
$q{\lfloor\frac{c}{2}\rfloor}$. Any two distinct quadratic functions on
$GF(q)$ coincide in at most two values, and hence $|M_f\cap M_g|\le       
%! an replaced by and
2{\lfloor\frac{c}{2}\rfloor}\le c$. Thus, our lists form a
$(q{\lfloor\frac{c}{2}\rfloor},q{\lfloor\frac{c}{2}\rfloor}-c)$-assignment.
Since the total number  $q^2\lfloor\frac{c}{2}\rfloor$ of colors is less
than $n$, this assignment is not feasible. Therefore $\zeta(K_n,c)
>q\lfloor\frac{c}{2}\rfloor=\sqrt{n\lfloor\frac{c}{2}\rfloor}-o(\sqrt{n})$.
\end{pf}

It will follow from Theorem~\ref{lll} that this bound (as a function of $n$
and $c$) is tight up to a multiplicative constant.


\section{Choosability versus maximum degree}\label{brsc}

In this section we prove a strengthening of Brooks's theorem, under the
condition that the intersections of the lists assigned to adjacent vertices
are bounded.

\begin{thm}\label{lll}
Let $\Delta(G)$ be the maximum degree of a vertex in a graph $G$. 
Then $\zeta(G,c)\le \lceil\sqrt{2\e c(\Delta(G)-1)}\rceil$, where
$\e=2.718\ldots$ is the Euler constant.
\end{thm}

\begin{pf}
Suppose lists of size $k\ge\sqrt{2\e c(\Delta(G)-1)}$ are assigned to the vertices
of $G$ in such a way that $|L(u)\cap L(v)|\le c$ whenever $uv\in E(G)$.
Consider a random coloring of $G$, that is every vertex $u$ is colored with
any color from $L(u)$ independently with probability $1\over k$. For every
edge $e\in E(G)$ we define the event $B(e)=\langle\mbox{\em the endpoints 
of\/ $e$
are colored with the same color}\rangle$. We have
$$Prob(B(e))\le {c\over k^2}$$
for every edge $e\in E(G)$. The line graph of $G$, $L(G)=(E(G),\{ef:e\cap f\neq
\emptyset\})$ serves as the dependency 
graph -- for every edge $e$, the event $B(e)$
is totally independent of the events $B(f)$ for edges $f$ 
which are nonadjacent to $e$ in the line 
graph $L(G)$. The maximum degree in the line graph is at most $2\Delta(G)-2$. 
Due to the choice of $k$, 
$$(2\Delta(G)-2)\cdot {c\over k^2}\le{1\over \e}$$
and therefore by the Lov\'asz Local Lemma (\cite{LLL}),
$$Prob(\mbox{$G$ is properly colored})=Prob(\bigwedge_{e\in E(G)}\overline{B(e)})>0.$$
It follows that there exists an admissible coloring.
\end{pf}


 As seen from Theorem~\ref{zscom3} for complete graphs, this bound
is best possible up to a multiplicative constant. Namely, we have the following
corollary.

\begin{cor}\label{infsup}
For every integer $c\ge 2$,
$$
\sqrt{\lfloor\frac{c}{2}\rfloor}
\le \liminf_{n\rightarrow\infty}\frac{\zeta(K_n,c)}{\sqrt{n}}\le
\limsup_{n\rightarrow\infty}\frac{\zeta(K_n,c)}{\sqrt{n}} \le 
\sqrt{2\e c}
.$$
\end{cor}

\begin{pf}
The first inequality is just repeated from Theorem~\ref{kvadrat}; the
last one follows from Theorem~\ref{lll} since $\Delta(K_n)=n-1$.
\end{pf}


\medskip\noindent
{\bf Problem 1.} Does there exist a limit 
$L=\lim_{n,c\rightarrow\infty}\frac{\zeta(K_n,c)}{\sqrt{nc}}$?            
%! c added
If yes,
determine the limit.
(Our bounds give $\sqrt{{1\over 2}}\le L\le \sqrt{2\e}$.)                   
%! c deleted
%an application of a slightly stronger version of the Local Lemma gives
%the upper bound $L\le \sqrt{2e}$.)


\section{Constructive bounds}\label{constr}

The sufficient condition for choosability in the previous section was proved by
probabilistic methods, and so far it is not known whether there exists a
polynomial-time deterministic coloring algorithm when the conditions hold.
Here we present another upper bound on the necessary length of lists, in terms
of maximum degree $\Delta$. This bound gives an improvement for not too large
$\Delta$ and also admits a polynomial-time coloring algorithm.

\begin{thm}\label{marcons}
Let $m=\max_{H\subseteq G}\lceil\frac{|E(H)|}{|V(H)|}\rceil$ for a graph $G$.
Then $\zeta(G,c)\le cm+1$, i.e., $G$ is
$(cm+1,1,c(m-1)+1)$-choosable and for any given assignment, an admissible
coloring can be found in polynomial time.
\end{thm}

\begin{pf}
Suppose that $m$ satisfies the assumptions and that lists
$L(u), u\in V(G)$ of size $cm+1$ are given. It is well known that
then the edges of $G$ can be oriented so that every vertex has outdegree
at most $m$. Such an orientation can be found in polynomial time, e.g.\ by
bipartite matching techniques. 
Let $A$ be the set of arcs in such an orientation.
For every vertex $u$,  delete those colors from $L(u)$ that occur in the lists 
of the
successors of $u$, i.e., define $L'(u)=L(u)
\setminus\bigcup_{v:uv\in A}L(v)$.
Assuming that lists assigned to adjacent vertices have intersections of
size at most $c$, we have $|\bigcup_{v:uv\in A}L(v)|\le mc$ and hence $L'(u)$
is nonempty for every $u\in V(G)$. Coloring $u$ with an arbitrary color
from $L'(u)$ yields a feasible coloring.
\end{pf}


\noindent
{\bf Remark.} In the same way, under the assumptions of Theorem~\ref{marcons},
 one can prove that $G$ is 
$(cm+t,t,c(m-1)+t)$-choosable for any $t\ge 1$.


\begin{cor}\label{brcons}
Let $\Delta=\Delta(G)$ and $k\ge {\Delta+2\over 2}$. Then $G$ is
$(k,1,k-1)$-choosable and for any given assignment, a feasible
coloring can be found in polynomial time.
\end{cor}

\begin{pf}
For any graph $G$ and any of its subgraphs $H$, $\frac{|E(H)|}{|V(H)|}\le
\frac{\Delta(H)}{2}\le\frac{\Delta(G)}{2}$. Hence, $m\le k-1$
and the result follows
from Theorem~\ref{marcons} for $c=1$.
\end{pf}

\begin{cor}\label{413}
Every planar graph is $(4,1,3)$-choosable, and a feasible coloring can be
found in polynomial time.
\end{cor}

\begin{pf}
Planar graphs satisfy $|E(H)|\le 3|V(H)|-6$, hence $m=3$. The result follows
from Theorem~\ref{marcons} for $c=1$.
\end{pf}

Examples of planar non-4-choosable graphs are known such that the
infeasible list assignments assign distinct lists to adjacent vertices. This
leaves a challenging open problem:

\medskip\noindent
{\bf Problem 2.} Is every planar graph $(4,1,2)$-choosable?


\medskip\noindent
{\bf Remark.} For $\Delta\le 16$, Corollary~\ref{brcons} gives a
better bound for $\zeta(G,1)$ than Theorem~\ref{lll}.                     
%! c replaced by 1


\begin{thebibliography}{AAA}

\bibitem{LLL}
P. Erd\H{o}s, L. Lov\'asz: Problems and results on 3-chromatic
hypergraphs and related questions, in: Infinite and Finite Sets (A. Hajnal,
L. Lov\'asz and V. S\'os, eds.), Colloq. Math. Soc. J. Bolyai 10, 
North-Holland,
Amsterdam, 1974, pp. 609--627

\bibitem{ERT}
P. Erd\H{o}s, A. Rubin, H. Taylor: Choosability in graphs, Congr. Numer.
26 (1979), 125--157

\bibitem{KTV}
J. Kratochv\'{\i}l, Zs. Tuza, M. Voigt: Choosing subsets from color sets
%Discrete Math. 
(to appear)


\bibitem{Th}
C. Thomassen: Every planar graph is 5-choosable,                          %!
J. Combin. Theory Ser. B 62 (1994), 180--181 

\bibitem {ZsM}
Zs. Tuza, M. Voigt: On a conjecture of Erd\H os, Rubin and Taylor,
Tatra Mountains Math. Publ. 9 (1996), 69--82                             %!

\bibitem{ma}
M. Voigt: List colourings of planar graphs,                               %!
Discrete Math. 120 (1993), 215--219                                  %!

\end{thebibliography}
\end{document}


\begin{pf}
Note that $k\ge {\Delta+2\over 2}$ is equivalent with $\Delta\le 2k-2$.
We will first prove that if $\Delta(G)\le\Delta$ and $\Delta\le 2k-2$
then $G$ is $(k,1,k-1)$-choosable by induction on
the number of vertices. The algorithm will then follow.

The statement is clear if $G$ has one vertex only.
Suppose $G$ is a minimal counterexample, i.e., there exists an
assignment $\cal L$ such that $G$ does not allow an ${\cal L}$-list
coloring. If there is a vertex, say $u$, such that $L(u)$ contains a
color that does not appear in the lists of the neighbors of $u$, we may
color $u$ with this color and color $G-\{u\}$ by induction hypothesis.

Assume on the other hand that for every vertex $u\in V(G)$ and every
color $c\in L(u)$, there is a neighbor $v$ of $u$ such that $c\in L(v)$.
Since $\Delta\le 2k-2$, every vertex $u$ is assigned at least two colors
that occur in the lists of exactly one neighbor of $u$ each. Consider
the auxiliary digraph $H$ with vertex set $V(H)=V(G)$ and arcs
$vu\in E(H)$ iff there is a color $c\in L(u)\cap L(v)$ such that $u$ is
the only neighbor of $v$ satisfying $c\in L(u)$. As we have reasoned
above, every vertex of $H$ has outdegree at least 2, and therefore $H$
contains a directed cycle of length greater than 2. Let $u_1,u_2,\ldots,
u_m$ be such a cycle. By the construction of $H$, for every
$i=1,2,\ldots,m$, there is a color $c_i\in L(u_i)\cap L(u_{i+1})$ such
that $u_{i+1}$ is the only neighbor of $u_i$ with $c_i\in L(u_{i+1})$.
It also follows that $c_i\neq c_{i+1}$ for every $i=1,2,\ldots,m$
(subscripts are considered modulo $m$). So we color vertex $u_i$ by
color $c_i$, $i=1,2,\ldots,m$, and delete the vertices of this cycle. By
induction hypothesis, the resulting graph allows a feasible coloring,
and no such coloring can be in conflict with the chosen coloring of the
cycle $u_1,u_2,\ldots,u_m$.

\medskip
The algorithm can be read directly from the proof:

\begin{description}
\item[{\bf Step 1}] {\bf If} there is a vertex $u$ and a color $c$ such 
that $c\in
L(u)$ and $c\not\in L(v)$ for every neighbor $v$ of $u$ \\
{\bf then} {\bf color}
$u$ with color $c$, {\bf set} $G=G-\{u\}$ and {\bf goto Step 1}\\
{\bf else goto Step 2}.
\item[{\bf Step 2}] {\bf If} $G$ is nonempty \\
{\bf then} find a cycle
$u_1,u_2,\ldots,u_m,\; m\ge 3$, such that there are colors
$c_i,i=1,2,\ldots,m$ such that $c_i\in L(u_i)\cap L(u_{i+1})$ and
$u_{i+1}$ is the only neighbor of $u_i$ satisfying $c_i\in L(u_{i+1})$,
$i=1,2,\ldots,m$. {\bf Color} $u_i$ with color $c_i$, $i=1,2,\ldots,m$,
{\bf set} $G=G-\{u_1,u_2,\ldots,u_m\}$ and {\bf goto~Step~1}.
\end{description}
\end{pf}



----- End Included Message -----


