  We give lower bounds on the communication complexity of graph problems in the
multi-party blackboard model. In this model, the edges of an $n$-vertex input
graph are partitioned among $k$ parties, who communicate solely by writing
messages on a shared blackboard that is visible to every party. We show that
any non-trivial graph problem on $n$-vertex graphs has blackboard communication
complexity $\Omega(n)$ bits, even if the edges of the input graph are randomly
assigned to the $k$ parties. We say that a graph problem is non-trivial if the
output cannot be computed in a model where every party holds at most one edge
and no communication is allowed. Our lower bound thus holds for essentially all
key graph problems relevant to distributed computing, including Maximal
Independent Set (MIS), Maximal Matching, ($\Delta+1$)-coloring, and Dominating
Set. In many cases, e.g., MIS, Maximal Matching, and $(\Delta+1)$-coloring, our
lower bounds are optimal, up to poly-logarithmic factors.
