A graph class is a predicate on finite simple graphs, where the vertex type may vary.

A graph \(H\) is a minor of \(G\), written \(H \preccurlyeq G\), if there is a minor model \(\varphi\) of \(H\) in \(G\): a map \(\varphi\) which assigns to every vertex \(v \in V(H)\) a connected subgraph \(\varphi(v) \subseteq G\) and to every edge \(e \in E(H)\) an edge \(\varphi(e) \in E(G)\) such that:

1. if \(u, v \in V(H)\) with \(u \neq v\) then \(V(\varphi(v)) \cap V(\varphi(u)) = \emptyset\), and
2. if \(e = uv \in E(H)\) then \(\varphi(e) = u'v' \in E(G)\) for vertices \(u' \in V(\varphi(u))\) and \(v' \in V(\varphi(v))\).

The set \(\varphi(v)\) is the branch set of \(v\).

The radius of a connected graph \(G\) is \(\operatorname{rad}(G) = \min_{u \in V(G)} \max_{v \in V(G)} \operatorname{dist}(u, v)\).

Let \(H\), \(G\) be graphs and let \(d \in \mathbb{N}\). The graph \(H\) is a depth-\(d\) minor of \(G\), written \(H \preccurlyeq_d G\), if there is a minor model \(\varphi\) of \(H\) in \(G\) such that the branch set \(\varphi(v)\) has radius at most \(d\) for all \(v \in V(H)\).

For a graph \(G\) and \(d \in \mathbb{N}\): \[\nabla_d(G) := \sup \left\{ \frac{|E(H)|}{|V(H)|} : H \preccurlyeq_d G \right\}, \qquad \omega_d(G) := \sup \left\{ t : K_t \preccurlyeq_d G \right\}.\] For a graph class \(\mathcal{C}\) and \(d \in \mathbb{N}\): \[\nabla_d(\mathcal{C}) := \sup_{G \in \mathcal{C}} \nabla_d(G), \qquad \omega_d(\mathcal{C}) := \sup_{G \in \mathcal{C}} \omega_d(G).\]

Let \(\nabla_d\) and \(\omega_d\) be as in Definition ShallowMinor.

A class \(\mathcal{C}\) of graphs has bounded expansion if \[\nabla_d(\mathcal{C}) < +\infty \qquad \text{for every } d \in \mathbb{N}.\] Equivalently, there is a function \(f \colon \mathbb{N} \to \mathbb{N}\) such that for all \(d \in \mathbb{N}\) and \(G \in \mathcal{C}\), we have \(\nabla_d(G) \leq f(d)\).

A class \(\mathcal{C}\) of graphs is nowhere dense if \[\omega_d(\mathcal{C}) < +\infty \qquad \text{for every } d \in \mathbb{N}.\] Equivalently, there is a function \(t \colon \mathbb{N} \to \mathbb{N}\) such that for all \(d \in \mathbb{N}\) and \(G \in \mathcal{C}\), we have \(\omega_d(G) \leq t(d)\).

A class that is not nowhere dense is called somewhere dense. Every bounded expansion class is nowhere dense.

Let \(G\) be a graph, let \(\sigma\) be a vertex ordering of \(G\), and let \(r \in \mathbb{N}\). For vertices \(u, v \in V(G)\) with \(u \leq_\sigma v\):

• \(u\) is strongly \(r\)-reachable from \(v\) if there is a path of length at most \(r\) from \(u\) to \(v\) whose every internal vertex \(w\) satisfies \(v <_\sigma w\).
• \(u\) is weakly \(r\)-reachable from \(v\) if there is a path of length at most \(r\) from \(u\) to \(v\) whose every internal vertex \(w\) satisfies \(u <_\sigma w\).

The sets of vertices strongly (resp. weakly) \(r\)-reachable from \(v\) are denoted \(\operatorname{SReach}_r[G, \sigma, v]\) (resp. \(\operatorname{WReach}_r[G, \sigma, v]\)).

The weak and strong \(r\)-coloring numbers of \(\sigma\) are then \[\begin{aligned} \operatorname{wcol}_r(G, \sigma) &\coloneqq \max_{v \in V(G)} |\operatorname{WReach}_r[G, \sigma, v]|, \\ \operatorname{scol}_r(G, \sigma) &\coloneqq \max_{v \in V(G)} |\operatorname{SReach}_r[G, \sigma, v]|. \end{aligned}\]

A vertex subset \(A \subseteq V(G)\) in a graph \(G\) is distance-\(r\) independent if any two different vertices \(a, b \in A\) are at distance larger than \(r\).

For a graph \(G\) and \(S \subseteq V(G)\), the graph \(G - S\) is obtained by removing all vertices of \(S\) and their incident edges. The vertex set remains \(V(G)\); vertices of \(S\) become isolated with no adjacencies.

A class of graphs \(\mathcal{C}\) is called uniformly quasi-wide if for every \(r \in \mathbb{N}\) there exists a function \(N_r \colon \mathbb{N} \to \mathbb{N}\) and a constant \(s_r \in \mathbb{N}\) such that for all \(m \in \mathbb{N}\), \(G \in \mathcal{C}\), and \(A \subseteq V(G)\) with \(|A| \geq N_r(m)\), there exists \(S \subseteq V(G)\) with \(|S| \leq s_r\) and \(B \subseteq A \setminus S\) with \(|B| \geq m\) such that \(B\) is distance-\(r\) independent in \(G - S\).