\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Uwe Schauz}
%
%
\medskip
\noindent
%
%
{\bf Flexible Color Lists in Alon and Tarsi's Theorem, and Time Scheduling with Unreliable Participants}
%
%
\vskip 5mm
\noindent
%
%
%
%
We present a purely combinatorial proof of Alon and Tarsi's Theorem
about list colorings and orientations of graphs. More precisely, we
describe a winning strategy for Mrs.\ Correct in the corresponding
coloring game of Mr.\ Paint and Mrs.\ \hbox{Correct}. This strategy
produces correct vertex colorings, even if the colors are taken from
lists that are not completely fixed before the coloration process
starts. The resulting strengthening of Alon and Tarsi's Theorem
leads also to strengthening of its numerous repercussions. For
example we study upper bounds for list chromatic numbers of
bipartite graphs and list chromatic indices of complete graphs. As
real life application, we examine a chess tournament time scheduling
problem with unreliable participants.
\bye