36 problems

Let $\mathcal{M}$ be a graph class that is proper, minor-closed, and union-closed. For graphs $G$ and $H$, write $G =_{\mathcal{M}} H$ when $\hom(K,G)=\hom(K,H)$ for every…

Minor-closed lower-bound conjecture. There exists a constant $c$ such that, for every real $d_0>0$, there exists a real $d\geq d_0$ and a proper minor-closed class with maximum ave…

Complete-minor-free girth conjecture.

A graph class $\mathcal{F}$ is proper if some graph is not isomorphic to any graph in $\mathcal{F}$. Write $int(\mathcal{F})$ for the class of intersection graphs of collections of…

Let $ll in N$ with $ll ge 2$, and let $q$ be the largest prime power with $q le ll$. For sufficiently large $t in N$, let $\falM$ be the class of matroids with no $U_{2,ll+2}$- or…

Let $\mathcal{G}$ be a graph class. The $\mathcal{G}$-treewidth conjecture. Elimination Distance to $\mathcal{G}$ should be fixed-parameter tractable when parameterized by…

Let $\mathcal{G}$ be a proper minor-closed graph class, and let $G$ be a connected $n$-vertex graph in $\mathcal{G}$. The spanning tree polytope of $G$ is the convex hull of the in…

Wood and Tóth's conjecture. Every graph excluding a fixed minor has crossing number

Frame-template conjecture. There exist $k\in\mathbb Z_+$ and frame templates $\Phi_1,\ldots,\Phi_s,\Psi_1,\ldots,\Psi_t$ such that $\mathcal{M}$ contains each class…

Perturbation conjecture. There exist $k,t\in\mathbb Z_+$ such that each vertically $k$-connected member of $\mathcal M$ is a rank-$(\leq t)$ perturbation of an $\mathbb F$-represen…

Matroid structure theorem. The stated tree-decomposition exists.

Let $t\geq 1$ be an integer. For a graph class $\mathcal{G}$, let $\operatorname{col}_\star(\mathcal{G})$ be the least integer $t$ for which there is a constant $C\geq 1$ such that…

Let $2\leq s\leq t$, let $0\leq p<t$, and write … Here, $K_r$ denotes the complete graph on $r$ vertices, $kK_t$ denotes the disjoint union of $k$ copies of $K_t$, and $G\vee H$ de…

Let $q$ be a prime power, and let $\mathcal{M}$ be a minor-closed class of $GF(q)$-representable matroids that does not include all graphs. For a matroid $M$, let $\chi_M(\lambda)$…

Let $M$ be a matroid. A frame matroid is a matroid of the form $M'\setminus B$, where $M'$ is framed by $B$. Let $U_{s,2s}$ be the uniform matroid, let $M^*$ denote the dual matroi…

Let $M$ be a matroid. For an integer $k$, $M$ is vertically $k$-connected if, for every $A\subseteq E(M)$ with $\lambda_M(A)<k-1$, either $A$ or $E(M)-A$ is spanning in $M$. Write…

Let $M$ be a matroid. For an integer $k$, $M$ is vertically $k$-connected if, for every $A\subseteq E(M)$ with $\lambda_M(A)<k-1$, either $A$ or $E(M)-A$ is spanning in $M$. Write…

Let $\mathcal{O}$ be a finite set of matroids such that $\operatorname{Ex}(\mathcal{O})$ is base-$q$ exponentially dense for some prime power $q$. Here $h_{\mathcal{M}}(n)$ denotes…

Let $\mathcal{G}$ be an addable, minor-closed class and let $\mathcal{U}\mathcal{G}$ be its corresponding collection of unlabelled graphs. Let $C_n \in_u \mathcal{U}\mathcal{C}_n$…

Let $\mathcal{G}$ be a minor-closed graph class that is both smooth, in the sense used in the paper for its labelled enumeration, and decomposable, meaning that membership is deter…

Let $\mathcal{G}$ be an addable, minor-closed class of graphs, let $G(z)$ be its exponential generating function, and let $\rho$ be the radius of convergence of $G(z)$.…

Let $\mathcal{G}$ be an addable, minor-closed class of graphs, and consider the set of limiting probabilities of $\textsc{MSO}$ sentences for the uniformly random graph…

Let $S$ be a fixed surface, let $\mathcal{G}$ be the class of all graphs embeddable on $S$, let $C_n \in_u \mathcal{C}_n$ be a random connected graph from $\mathcal{G}$, and let…

Growth Rate Conjecture. For every integer $a ge 1$, there is an integer $c>0$ such that at least one of the following holds:

Let $\mathrm{Ex}(C_{2\ell})$ and $\mathrm{Ex}(C_{2\ell-1})$ denote the classes of graphs with no $C_{2\ell}$ and no $C_{2\ell-1}$ minor, respectively, and let $\Delta_n$ denote the…