  We study the problem of coloring a given graph using a small number of colors
in several well-established models of computation for big data. These include
the data streaming model, the general graph query model, the massively parallel
computation (MPC) model, and the CONGESTED-CLIQUE and the LOCAL models of
distributed computation. On the one hand, we give algorithms with sublinear
complexity, for the appropriate notion of complexity in each of these models.
Our algorithms color a graph $G$ using about $\kappa(G)$ colors, where
$\kappa(G)$ is the degeneracy of $G$: this parameter is closely related to the
arboricity $\alpha(G)$. As a function of $\kappa(G)$ alone, our results are
close to best possible, since the optimal number of colors is $\kappa(G)+1$.
  On the other hand, we establish certain lower bounds indicating that
sublinear algorithms probably cannot go much further. In particular, we prove
that any randomized coloring algorithm that uses $\kappa(G)+1$ many colors,
would require $\Omega(n^2)$ storage in the one pass streaming model, and
$\Omega(n^2)$ many queries in the general graph query model, where $n$ is the
number of vertices in the graph. These lower bounds hold even when the value of
$\kappa(G)$ is known in advance; at the same time, our upper bounds do not
require $\kappa(G)$ to be given in advance.
