  Recent breakthroughs in graph streaming have led to the design of single-pass
semi-streaming algorithms for various graph coloring problems such as
$(\Delta+1)$-coloring, degeneracy-coloring, coloring triangle-free graphs, and
others. These algorithms are all randomized in crucial ways and whether or not
there is any deterministic analogue of them has remained an important open
question in this line of work.
  We settle this fundamental question by proving that there is no deterministic
single-pass semi-streaming algorithm that given a graph $G$ with maximum degree
$\Delta$, can output a proper coloring of $G$ using any number of colors which
is sub-exponential in $\Delta$. Our proof is based on analyzing the multi-party
communication complexity of a related communication game, using random graph
theory type arguments that may be of independent interest.
  We complement our lower bound by showing that just one extra pass over the
input allows one to recover an $O(\Delta^2)$ coloring via a deterministic
semi-streaming algorithm. This result is further extended to an $O(\Delta)$
coloring in $O(\log{\Delta})$ passes even in dynamic streams.
