  Differential privacy is the gold standard in the problem of privacy
preserving data analysis, which is crucial in a wide range of disciplines.
Vertex colouring is one of the most fundamental questions about a graph. In
this paper, we study the vertex colouring problem in the differentially private
setting.
  To be edge-differentially private, a colouring algorithm needs to be
defective: a colouring is d-defective if a vertex can share a colour with at
most d of its neighbours. Without defectiveness, the only differentially
private colouring algorithm needs to assign n different colours to the n
different vertices. We show the following lower bound for the defectiveness: a
differentially private c-edge colouring algorithm of a graph of maximum degree
{\Delta} > 0 has defectiveness at least d = {\Omega} (log n / (log c+log
{\Delta})).
  We also present an {\epsilon}-differentially private algorithm to {\Theta} (
{\Delta} / log n + 1 / {\epsilon})-colour a graph with defectiveness at most
{\Theta}(log n).
