Separability Properties of Monadically Dependent Graph Classes
Abstrakt
A graph class C is monadically dependent if one cannot interpret all graphs in colored graphs from C using a fixed first-order interpretation. We prove that monadically dependent classes can be exactly characterized by the following property, which we call flip-separability: for every r in N, epsilon > 0, and every graph G in C equipped with a weight function on vertices, one can apply a bounded (in terms of C, r, epsilon) number of flips (complementations of the adjacency relation on a subset of vertices) to G so that in the resulting graph, every radius-r ball contains at most an epsilon-fraction of the total weight. On the way to this result, we introduce a robust toolbox for working with various notions of local separations in monadically dependent classes.