197 problems

Let $H$ be the graph obtained from $K_7$ by deleting two independent edges. Every $5$-connected graph $G$ on $n\ge 7$ vertices with $|E(G)|\ge 4n-9$ contains $H$ as a minor.

$\exists C>0\ \forall g\ge 1\ \forall n\ge 1\ \forall G$, if $G$ is an $n$-vertex graph embeddable on an orientable surface of genus $g$ and has maximum degree $\Delta$, then…

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…

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 $K_t$ be the complete graph on $t$ vertices, and call a graph $K_t$-minor-free if it has no $K_t$ minor. A graph is $k$-colourable if it has a proper colouring using at most…

Odd Hadwiger conjecture. If

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…

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…

Minor-closed-family conjecture. There exists a function $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $f(n)=n^{1+o(1)}$ and, for every minor-closed family of graphs $\mathcal{G}$,

Weak Hadwiger conjecture. Every graph $G$ with $\alpha(G)\leq 2$ contains

Jørgensen's conjecture. If $G$ is 6-connected and does not have a $K_6$ minor, then $G$ is apex.

Dominating Hadwiger's Conjecture. For every integer $t\geq 1$, every graph with no dominating $K_t$ minor is $(t-1)$-colorable.

Odd-minor Duchet–Meyniel conjecture. For any graph $G$ of order $n$,

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 $G$) be a 3-connected non-Hamiltonian graph. Let $K_{3,4}$ be the complete bipartite graph, let $\mathfrak{Q}^+$ be obtained from the cube by adding a new vertex adjacent to th…

Let $p,q\geqslant 1$ be integers. Define $\ell(p,q)$ to be the minimum integer such that every graph $G$ with treewidth at least $\ell(p,q)$ contains pairwise disjoint connected su…

Let $a$ and $b$ be integers with $b\geqslant a\geqslant 2$, and write … For graphs, let $A_0(G)=A(G)$, let $K_{a-1}\vee (kK_b\cup K_t)$ denote the join of $K_{a-1}$ with the disjoi…

Let $K_t$ be the complete graph on $t$ vertices, and call a graph $K_t$-minor-free if it has no $K_t$ minor. A list assignment $L$ assigns a set of permissible colours $L(v)$ to ea…

Let $t\in\mathbb{N}$ and let $G$ be a graph. A $K_t$-minor-free graph is a graph that does not contain a $K_t$-minor, and $\chi_\ell(G)$ denotes its list chromatic number. The…

Let $(G,-)$ be a signed graph whose underlying graph is $G$, with every edge negative, and let $(K_{k+1},-)$ denote the complete graph on $k+1$ vertices with every edge negative. A…

Let $\mathcal{X}_{k,c}$ be the graph family defined in the source, and let $\mathcal{M}$ be a minor-closed class. NSSW excluded-configuration conjecture. Every minor-closed class t…

A finite simple graph $G$ is double-critical if it is connected and, for every edge $uv\in E(G)$, $\chi(G-\{u,v\})=\chi(G)-2$. A graph $H$ is a minor of $G$ if it can be obtained f…

Polynomial-time branchwidth conjecture. Branchwidth can be computed in polynomial time on $H$-minor-free graphs.

Let $\mathcal F$ be the class of graphs $G$ such that no component of $G$ contains every finite graph as a minor. A graph $U$ is $<$-universal for a class if every graph in the cla…