Clustering Powers of Sparse Graphs

We prove that if \(G\) is a sparse graph — it belongs to a fixed class of bounded expansion \(C\) — and \(d ∈ N\) is fixed, then the \(d\)th power of \(G\) can be partitioned into cliques so that contracting each of these clique to a single vertex again yields a sparse graph. This result has several graph-theoretic and algorithmic consequences for powers of sparse graphs, including bounds on their subchromatic number and efficient approximation algorithms for the chromatic number and the clique number.