Abstract: The greatest reduced average density, grad with rank r of a graph G is defined ∇r(G)=max |E(H )| / |V(H )| where the maximum is taken over all the minors H of G obtained by contracting a set of vertex-disjoint subgraphs with radius at most r and then arbitrarily deleting vertices and edges. A class of graphs C has bounded expansion if supG∈C ∇r(G)<∞ (for any integer r). For instance, for any fixed graph H the class of the graphs with no subdivision of H has bounded expansion. Consequently, proper minor closed classes of graphs and classes of graphs with bounded degree have bounded expansion.
The tree-depth td(G) of graph G is the minimum height of a rooted forest which closure contains G as a subgraph. For a graph G and a positive integer p, we define &chip(G) as the minimum number N , such that the vertex set of G has a partition into N parts, each i≤ p of them inducing a subgraph of G with tree-depth at most 1. Hence χ1 (G) = 1 and χ2 (G) is the usual chromatic number. We proved that χp (G) is bounded by Fp (&nablapp(G)) (the needed rank has been improved from pp to 2p independently by X. Zhu and Z. Dvorak using probabilist arguments). Moreover, a partition of the vertex set of G into Fp (&nablapp(G)) parts, each i≤ p of them inducing a subgraph of tree-depth at most i, may be computed in time O( Fp (&nablapp(G))n), where n is the order of G. We survey recent consequences of this results, either theoretical (homomorphism bounds, coloring properties, existence of indegree bounded fraternal augmentations) or algorithmic (linear time algorithm to count the isomorphs of a fixed pattern in a graph, linear time decidability of homorphism monotone first order properties).