A graph class is a set of finite simple graphs. A class contains, for each number of vertices n, some of the simple graphs on the canonical n-element vertex type.

A graph class is a class $\mathcal{F}$ of finite simple graphs which is closed under isomorphism: if $F \in \mathcal{F}$ and $F \cong F'$, then $F' \in \mathcal{F}$.

Graph classes are ordered by inclusion, $\mathcal{F} \subseteq \mathcal{F}'$, written $\mathcal{F} ≤ \mathcal{F}'$. The intersection $\bigcap_{i \in I} \mathcal{F}_i$ and the union $\bigcup_{i \in I} \mathcal{F}_i$ of a family of graph classes are again graph classes, written $⨅ i, \mathcal{F} i$ and $⨆ i, \mathcal{F} i$.

Five closure properties of a class $\mathcal{F}$ of finite simple graphs.

$\mathcal{F}$ is closed under taking summands if $F_1 + F_2 \in \mathcal{F}$ implies $F_1 \in \mathcal{F}$ and $F_2 \in \mathcal{F}$, where $+$ denotes disjoint union, and union-closed if conversely $F_1, F_2 \in \mathcal{F}$ implies $F_1 + F_2 \in \mathcal{F}$. It is minor-closed if every minor of a member is a member.

It is closed under taking induced subgraphs if every induced subgraph of a member is a member, and closed under contracting edges if every graph obtained from a member by contracting edges is a member.

A graph parameter assigns a natural number to every finite simple graph. Two graph parameters p and q are functionally equivalent when each is bounded by a numerical function of the other: there are functions f, g : ℕ → ℕ such that every finite simple graph G satisfies both p(G) ≤ f(q(G)) and q(G) ≤ g(p(G)). Functionally equivalent parameters are bounded on exactly the same classes of graphs.

A finite path graph is a graph isomorphic to the standard path graph on a positive number of vertices.

A star has a centre adjacent to every other vertex and has no edges between two non-central vertices.

A tree is a connected acyclic simple graph, using mathlib's native $SimpleGraph.IsTree$ predicate.

A finite ladder is a nonempty two-row grid: two paths joined by corresponding rungs.

A triangle is a finite complete graph on exactly three vertices.

An outerplanar graph is maximal outerplanar when no edge can be added between its existing vertices while preserving outerplanarity.

A graph is outerplanar here when it has a crossing-free straight-line drawing with every vertex on one circle, a compact certificate for having every vertex on the boundary of the outer face.

A finite two-terminal series-parallel graph is built from a single terminal edge by series and parallel composition. The side conditions say that the composed graphs meet only at the intended terminals, and the final support condition excludes unused isolated vertices.

A triangulation of a graph G is a planar supergraph T on the same vertex set, with at least three vertices, to which no edge can be added while preserving planarity. For a plane embedding this is equivalent to every face of T being bounded by a triangle.

A nonempty rectangular grid has vertices in rows and columns, with edges between orthogonally consecutive positions. A wall is the brick-wall subgraph obtained by retaining alternating vertical grid edges.

A graph is planar here when it has a crossing-free straight-line drawing in the real plane. For finite simple graphs, this agrees with the usual notion of planarity. The drawing certificate is supplied by a separate concept.

A class of finite simple graphs is χ-bounded if the chromatic number of each graph in the class is bounded by a function of its clique number.

Let $G=(V,E)$ be a finite undirected simple graph. A feedback vertex set is a set $S\subseteq V$ for which the induced graph $G[V\setminus S]$ is acyclic. The feedback vertex number is

The minimum exists because deleting all vertices leaves an acyclic graph.

Let $G=(V,E)$ be a finite undirected simple graph. A feedback edge set is a set $F\subseteq E$ for which the graph $G-F$, obtained by deleting the edges in $F$ and retaining all vertices, is acyclic. The feedback edge number is

The minimum exists because deleting all edges leaves an acyclic graph.

Fix a linear ordering of the vertices of a graph G. An admissible family of size k at a vertex v consists of k paths of length at most r that start at v, end at vertices smaller than v, and are pairwise disjoint apart from v. The r-admissibility adm_r(G) is the minimum over all orderings of the largest k + 1 for which some vertex of G carries an admissible family of size k. Counting v itself is the usual convention: it makes admissibility at least 1 and at most the strong r-coloring number.

This is Definition 2.2 of Chapter 2 of the source lecture notes (2019/20 edition), minimized over vertex orderings as in their Definition 2.3; the notes give the same rationale for the +1, namely consistency with the reachability sets, which contain the vertex itself.

Fix a linear ordering of the vertices of a graph G. A vertex u is weakly r-reachable from v if some path from v to u of length at most r has u as its smallest vertex, and strongly r-reachable from v if some path from v to u of length at most r has v as its smallest vertex apart from u itself. The weak r-coloring number wcol_r(G) and the strong r-coloring number scol_r(G) are the minima, over all orderings, of the largest number of vertices weakly respectively strongly r-reachable from a single vertex. A graph class has subpolynomial weak coloring numbers if for every radius r and every ε > 0 there is a constant c such that every subgraph H of a member, on m vertices, satisfies wcol_r(H) ≤ c · m^ε.

Weak and strong reachability are Definition 2.1, and the two coloring numbers Definition 2.3, of Chapter 2 of the source lecture notes (2019/20 edition), which write scol_r where the earlier 2017/18 edition writes col_r. The subpolynomial bound is the conclusion of Theorem 3.4 of that chapter.

The neighborhood complexity of a graph G on a vertex set A counts the distinct traces of vertex neighborhoods on A, that is, the sets N(v) ∩ A for v ranging over all vertices of G. A graph class has almost linear neighborhood complexity if for every ε > 0 there is a constant c such that every member G and every nonempty vertex subset A leave at most c · |A|^(1+ε) traces — neighborhood complexity |A|^(1+o(1)).

For a finite simple graph $G$ and a natural number $p$, the neighbourhood complexity $π_G(p)$ is the maximum, over sets $X$ of $p$ vertices, of the number of distinct traces on $X$ of the neighbourhoods of vertices outside $X$. A graph class has linear neighbourhood complexity if $π_G(p)$ is bounded by a constant multiple of $p$ for every positive $p$.

A finite graph is a cograph if it has twin-width zero. Equivalently, it can be reduced to one vertex by repeatedly contracting a pair of twins, without ever creating a red edge.

A graph $H$ is an induced minor of $G$ if its vertices have pairwise disjoint, nonempty connected branch sets in $G$, and two distinct branch sets are joined by an edge exactly when their vertices are adjacent in $H$. Thus edges between retained branch sets cannot be deleted. For finite graphs this is the usual definition by vertex deletions and edge contractions.

The $k\times k$ square grid is the Cartesian product of two $k$-vertex paths. A graph excludes the induced grid of size $k$ if this square grid is not an induced minor of the graph.

A graph class is a set of finite simple graphs: for each number of vertices n, some of the simple graphs on the canonical n-element vertex type. A graph class is weakly sparse if some complete bipartite graph $K_{t,t}$ occurs in no member as a subgraph.

A graph H is a minor of a graph G when the vertices of H can be represented by pairwise disjoint connected branch sets in G, with an edge joining the corresponding branch sets for every edge of H.

A graph H is a topological minor of G when the vertices of H are represented by distinct branch vertices of G and its edges by paths whose interiors contain no branch vertex and are pairwise disjoint. Equivalently, G contains a subdivision of H as a subgraph.

A nonempty rectangular grid has vertices in rows and columns, with edges between orthogonally consecutive positions. A wall is the brick-wall subgraph obtained by retaining alternating vertical grid edges.

A graph is outerplanar here when it has a crossing-free straight-line drawing with every vertex on one circle, a compact certificate for having every vertex on the boundary of the outer face.

A graph is planar here when it has a crossing-free straight-line drawing in the real plane. For finite simple graphs, this agrees with the usual notion of planarity. The drawing certificate is supplied by a separate concept.

A triangulation of a graph G is a planar supergraph T on the same vertex set, with at least three vertices, to which no edge can be added while preserving planarity. For a plane embedding this is equivalent to every face of T being bounded by a triangle.

A k-division of $Fin n$ partitions it into k nonempty consecutive intervals in increasing order. A row division and a column division split a matrix into a grid of k² cells. A cell is vertical if each of its columns is constant, horizontal if each of its rows is constant, and mixed if it is neither. The matrix has a k-mixed minor if some pair of row and column k-divisions makes all k² cells mixed, and its mixed number is the largest such k.

An ordering of a finite simple graph's vertices turns its adjacency relation into such a matrix. The mixed minor number of the graph is the least mixed number of this matrix over all vertex orderings.

A set A of vertices is distance-r independent in G if any two distinct vertices of A are at distance more than r. A graph class is uniformly quasi-wide if for every radius r there are a threshold function N and a separator bound s such that in every member G, every vertex set A of size at least N(m) contains a distance-r independent subset of size at least m of G − S, for some set S of at most s vertices.

This is Definition 3.1 of Chapter 4 of the source lecture notes (2019/20 edition), where the constants s are called the margins and the functions N the wideness functions.

A graph G has depth-r density at most d if every depth-r minor H of G has at most d · |V(H)| edges — the standard "grad" bound on how dense the shallow minors of a sparse graph can be. A graph class has subpolynomial density if for every depth r and every ε > 0 there is a constant c such that every depth-r minor H of a member, on m vertices, has at most c · m^(1+ε) edges: shallow-minor edge counts m^(1+o(1)).

Definition 2.4 of Chapter 1 of the source lecture notes (2019/20 edition) defines the grad ∇r(G) as the supremum of |E(H)|/|V(H)| over the depth-r minors H of G, so the per-graph predicate here says ∇r(G) ≤ d.

A graph H is a depth-r topological minor of a graph G if the graph obtained from H by subdividing every edge at most 2r times is a subgraph of G: the vertices of H are realized by distinct principal vertices of G, and every edge of H by a path of length at most 2r+1 between the principal vertices of its endpoints, these paths being internally disjoint from each other and from all principal vertices. A graph G has depth-r topological density at most d if every depth-r topological minor H of G has at most d · |V(H)| edges.

In the source lecture notes these are Definitions 2.15 and 2.16 of Chapter 1 (2019/20 edition): the topological minor relation is written H ⪯^top_r G, and the topological grad ∇̃_r(G) is the supremum of |E(H)|/|V(H)| over the depth-r topological minors H of G, so the density predicate here says ∇̃_r(G) ≤ d. The length bound 2r+1 is the notes' own convention, chosen so that a depth-r topological minor is in particular a depth-r minor.

A graph H is a depth-r minor of a graph G if H can be obtained from G by deleting vertices and edges and contracting pairwise disjoint connected subgraphs of radius at most r. A graph class is nowhere dense if for every depth r there is a t such that no member has the complete graph on t vertices as a depth-r minor.

The source lecture notes give these as Definitions 2.3 and 2.6 of Chapter 1 (2019/20 edition), writing H ⪯r G for the depth-r minor relation. Nowhere denseness is stated there as ωr(C) < ∞ for every r, with the excluded-clique form used here spelled out immediately after as an equivalent.

A graph class is monadically dependent (also called monadically NIP) if it does not transduce the class of all graphs.

A tree is a connected acyclic simple graph, using mathlib's native $SimpleGraph.IsTree$ predicate.

A tree decomposition of a finite simple graph G consists of a finite tree T and a bag of graph vertices at each node such that every graph vertex occurs in a bag, the endpoints of every graph edge occur together in a bag, and the nodes whose bags contain any fixed vertex induce a connected subgraph of T.

The treewidth of G is the least w such that G has a tree decomposition with every bag of size at most w + 1.