25 problems

Kelmans–Seymour conjecture. Every 5-connected nonplanar graph contains $TK_5$.

Robertson's conjecture. There is only one minimal antichain based on $2$-multiples of paths.

Let a Robertson chain of length $k$ be the graph obtained from a path of length $k$ by duplicating each edge. A graph contains another graph as a topological minor if the latter ca…

A graph is 5-connected if deleting fewer than five vertices leaves it connected, and it is nonplanar if it cannot be drawn in the plane without crossings. A $K_5$-subdivision is a…

Erdős–Fajtlowicz conjecture.

An $\ell$-lift of $K_n$ is obtained by replacing every vertex of $K_n$ with an independent set of size $\ell$ and every edge with a matching of size $\ell$ between the correspondin…

An $\ell$-lift of a graph $G$ is obtained by replacing every vertex of $G$ with an independent set of size $\ell$, and replacing each edge by a matching of size $\ell$ between the…

Let $G$ and $H$ be graphs, and let $k\geqslant 0$ be a half-integer. A graph $H$ is a $k$-shallow topological minor of $G$ if a subgraph of $G$ is isomorphic to a subdivision of…

Let $D$ be a digraph, let $\vec{\chi}(D)$ denote its dichromatic number, and let $\accentset{\leftrightarrow}{C}_\ell$ denote the bioriented cycle of length $\ell$. Bioriented-cycl…

Let $\accentset{\leftrightarrow}{K}_n$ denote the bioriented complete digraph on $n$ vertices, and let $\operatorname{mader}_{\vec{\chi}}(F)$ be the smallest integer $k\ge1$ such t…

Let $C_\ell$ be the undirected cycle of length $\ell$, and let $C$ be an orientation of $C_\ell$. For a digraph $F$, let $\operatorname{mader}_{\vec{\chi}}(F)$ be the smallest inte…

Let $t$ be a positive integer. A graph is properly $t$-colorable if its vertices can be partitioned into $t$ edgeless induced subgraphs. An $H$-minor is a graph structure obtained…

Let $k$ be a positive integer. Let $G_1,G_2,\ldots$ be graphs that do not contain a Robertson chain of length at least $k$ as a topological minor. Let $Q$ be a set equipped with a…

A graph contains another graph as a topological minor if the latter can be obtained from a subgraph of the former by repeatedly contracting edges incident with vertices of degree t…

Let $K_h$ denote the complete graph on $h$ vertices, and consider graph classes that exclude $K_h$ as a topological subgraph. An algorithm is said to solve the isomorphism problem…

Topological Tree Alternative Conjecture. For a given locally finite tree $T$, the number of isomorphism classes of trees that are mutually topological minors with $T$ is either $1$…

Chain-length conjecture. For every ordinal $\alpha<\omega_2$, there is a chain of locally finite trees of length $\alpha$.

Fox–Lee–Sudakov conjecture. There is a constant $c>0$ such that every graph $G$ with $\chi(G)=k$ satisfies

Mader's density question. Does every such graph with more than $12(n-2)/5$ edges contain $K_4^-$, $K_{2,3}$, or $TK_5$?

Mader's conjecture. Every simple graph with minimum degree at least $5$ and no $K_4^-$ contains $TK_5$.

Dirac's conjecture. If $G$ has at least $3n-5$ edges, then $G$ contains $TK_5$.

Kelmans–Seymour conjecture. If $G$ does not contain $TK_5$, then $G$ is planar or admits a cut of size at most $4$.

Seymour–Kelmans conjecture. Every 5-connected graph without a $K_5$ topological minor is planar.

Planar-or-bounded-high-degree conjecture. There exist constants $D$ and $a$ such that every graph $G$ that does not contain $K_5$ as a topological minor can be expressed as a cliqu…

Let $G$ be an $r$-critical graph on $r+o(r)$ vertices, where an $r$-critical graph has chromatic number $r$ and every proper subgraph has smaller chromatic number. A graph satisfie…