347 problems

Let $G$ be a finite graph and let $t\in\mathbb{N}$. A minor of $G$ is a graph obtainable from $G$ by a sequence of vertex deletions, edge deletions, and edge contractions; write…

Fat minor conjecture. For every graph $X$ there exists a function $f:\mathbb{N}\to\mathbb{N}^2$ such that, for every graph $G$ and $K\in\mathbb{N}$, if $G$ does not contain $X$ as…

Tutte's conjecture. Every nonplanar snark $G$ has the Petersen graph as a minor.

Let $t\in\mathbb{N}$, let $K_t$ be the complete graph on $t$ vertices, and let $\chi(G)$ denote the chromatic number of a graph $G$. The linear Hadwiger conjecture. There is an abs…

Let $G$ be a 6-connected simple graph. A graph is 1-apex if deleting one vertex makes it planar, and $K_6$ denotes the complete graph on six vertices. Jørgensen's conjecture. Every…

Let $G$ be a graph and let $t$ be a positive integer. An odd-minor of a graph is a graph formed from a subgraph by contracting edge cuts; odd-minors preserve the parity of cycles.…

Let finite graphs be ordered by the minor relation. Wagner's conjecture. Every minor-closed class of finite graphs is determined by a finite set of excluded minors. Robertson and S…

Signed-graph $K_5$-minor conjecture. Any signed graph $(G,\sigma)$ which has neither a $(K_5,-)$-minor nor induces an element of $\mathcal{O}_{k+1}$ maps to $SPC(k)$.

Let a graph be well-quasi-ordered (WQO) under the minor relation when every infinite sequence of graphs contains two graphs such that an earlier one is a minor of a later one. Thom…

Let $(G,-)$ be the signed graph obtained from a graph $G$ by assigning a negative sign to every edge, and let $(K_t,-)$ be the all-negative signed complete graph. A signed graph mi…

Let a graph have finite tree-width if its tree-width is finite, and consider the minor relation on graphs. Finite-tree-width well-quasi-ordering conjecture. The graphs of finite tr…

Andreae's ubiquity conjecture. Every locally finite graph is ubiquitous.

Let $K_{s,t}$ be the complete bipartite graph with parts of sizes $s$ and $t$, where $s$ is fixed, and let $c(K_{s,t})$ denote the supremum of the density of graphs having no…

All graphs in this paper are finite and simple. Let $\omega(G)$ denote the clique number and $\chi(G)$ the chromatic number. For graphs $G_1$ and $G_2$, write $G_i\succcurlyeq K_r$…

Duchet–Meyniel conjecture. Every graph $G$ of order $n$ has a $K_{\lceil n/\alpha(G)\rceil}$ minor.

Gerards–Seymour odd Hadwiger conjecture. For all $t\geq 2$, every graph with no odd $K_t$ minor is $(t-1)$-colorable.

Let $G$ be a finite simple graph, and let $\chi(G)$ denote its chromatic number. For positive integers $\ell$ with $\ell<\chi(G)$, let $K_{\ell,\chi(G)-\ell}$ be the complete bipar…

Mattman–Pierce conjecture. The obstruction set $\operatorname{obs}(\mathcal{C}_k^{\mathcal{K}})$ contains the $Y\Delta Y$-families of $K_{n+5}$ and $K_{3^2,2^n}$.

Let $H$ be a graph, let $\mathcal{G}_H$ be the class of graphs with no $H$ minor, and let $\operatorname{\overline{td}}(H)$ denote the connected tree-depth of $H$. Let…

Let $s,t\ge 1$ be integers, and let $f_\ell(H)$ denote the maximum list chromatic number of an $H$-minor-free graph. Woodall's conjecture. Every $K_{s,t}$-minor-free graph is…

Let $t$ be a positive integer and let $G$ be a graph. A $K_t$ minor is a minor of $G$ isomorphic to the complete graph on $t$ vertices. A graph is $ct$-colourable if its vertices c…

Let $G$ be a graph and let $I_G$ be its cut ideal. A graph is $K_5$-minor-free when it has no minor isomorphic to $K_5$. Quartic generation conjecture. … This extends the proposed…

Let $H$ be a fixed graph. Fiorini–Joret–Theis–Wood conjecture. Any $n$-vertex graph whose average degree is only slightly above the threshold required to guarantee an $H$-minor has…

Let $G$ be a finite simple graph. A connected matching is a matching $M\subseteq E(G)$ such that for every two edges $e,f\in M$, an endpoint of $e$ is adjacent to an endpoint of…

Coarse Kuratowski conjecture. Graphs forbidding $K_5$ and $K_{3,3}$ as $K$-fat minors are quasi-isometric to planar graphs.