Clustering powers of sparse graphs

03/07/2020
by   Jaroslav Nešetřil, et al.
0

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 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset