Private graph colouring with limited defectiveness

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 {Δ} > 0 has defectiveness at least d = {Ω} (log n / (log c+log {Δ})). We also present an {ε}-differentially private algorithm to {Θ} ( {Δ} / log n + 1 / {ε})-colour a graph with defectiveness at most {Θ}(log n).