12 problems

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…

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 $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…

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…

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$…

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

Hajós' conjecture. Every graph containing no $TK_5$ is 4-colorable.

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…