Clustering powers of sparse graphs (Q2209886)

Summary: We prove that if \(G\) is a sparse graph -- it belongs to a fixed class of bounded expansion \(\mathcal{C}\) -- and \(d\in \mathbb{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.