Abstrakt
We prove that if G is a sparse graph - it belongs to a fixed class of bounded expansion C - and d is an element of N is fixed, then the dth 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.