43 problems

Let $G$ be a graph, let $\chi(G)$ denote its chromatic number, and let $K_{\chi(G)}$ be the complete graph on $\chi(G)$ vertices. A weak immersion of a graph $H$ in $G$ consists of…

Let $G$ be a graph with independence number $\alpha(G)=2$, let $\chi(G)$ denote its chromatic number, and let $K_{\chi(G)}$ be the complete graph on $\chi(G)$ vertices. A weak imme…

Let $G$ be a loopless simple graph, let $\chi(G)$ denote its chromatic number, and let $K_t$ be the complete graph on $t$ vertices. A strong immersion of $K_t$ in $G$ is an immersi…

Let $G$ and $H$ be graphs, and let $\operatorname{im}(G)=t$ and $\operatorname{im}(H)=r$, where $\operatorname{im}$ denotes the immersion number. Let $G\boxtimes H$ be their strong…

Weak knitwork immersion conjecture. The class $\mathbf{T}(k,d,\Delta,\ell;\Omega)$ is well-quasi-ordered by $\Omega$-knitwork immersion.

Weak immersion conjecture. The class of Eulerian digraphs is well-quasi-ordered by weak immersion.

Johnson's conjecture. For every $d\geq 1$, the class of Eulerian digraphs of maximum degree $2d$ is well-quasi-ordered by strong immersion.

Let $t\in\mathbb{Z}^+$ and let $G$ be a graph. An immersion of $K_t$ is strong odd if its paths are pairwise edge-disjoint, have odd length, and no terminal is an interior vertex o…

Let $G$ be a graph, and let $t\in\mathbb{Z}^+$. Suppose that $\alpha(G)\leq 2$ and $G$ has no strong odd $K_t$-immersion. Improved constant conjecture. The constant $\tfrac{3}{2}$…

Let $G$ be a graph and let $G\xrightarrow{\operatorname{odd}} K_{ct}$ mean that $G$ admits a $t'$-oddomorphism to $K_{ct}$, as defined in the source. Linear immersion conjecture. T…

Let $\mathcal{M}_1$ and $\mathcal{M}_2$ be two distinct immersion-closed and union-closed graph classes. For graphs $G$ and $H$, write $G =_{\mathcal{M}} H$ when…

Let $G$ be a graph and let $t$ be a positive integer. A strong immersion of $K_t$ in $G$ maps the vertices of $K_t$ to vertices of $G$ that are not internal vertices of the edge-di…

Let $G$ be a graph and let $t$ be a positive integer. An immersion of $K_t$ in $G$ maps the vertices of $K_t$ to distinct vertices of $G$ and its edges to edge-disjoint trails betw…

Let $G$ be a finite, undirected, loopless graph, and let $\chi(G)$ denote its chromatic number. A graph $H$ is a totally odd immersion of $G$ when the edges of $H$ are represented…

For a graph $G$, let $\operatorname{toi}(G)$ be the maximum integer $t$ such that $G$ contains a totally odd strong immersion of $K_t$, and let $\chi(G)$ denote its chromatic numbe…

Let $G$ be a graph, let $\chi(G)$ denote its chromatic number, and let $K_t$ be the complete graph on $t$ vertices. An $H$-immersion is an injective mapping of $V(H)$ to $V(G)$ tog…

Let $r$ be a positive integer, and let $C_{2,r}$ denote the double cycle of length $r$, obtained from a cycle on $r$ vertices by adding a parallel edge to each edge of the cycle. A…

Let $t$ be an integer, and let $G$ be a graph. A $K_t$-immersion-free graph is a graph containing no immersion of the complete graph $K_t$. Lescure–Meyneil–Abu-Khzam–Langston conje…

Let $G$ be a graph, let $\chi(G)$ be its chromatic number, and let $K_k$ denote the complete graph on $k$ vertices. Clique-immersion conjecture. If … then $G$ contains a $K_k$-imme…

Totally odd strong immersion conjecture. Every graph $G$ with $\chi(G)\ge t$ contains a totally odd strong immersion of $K_t$.

Churchley's conjecture. Every graph $G$ with $\chi(G)\ge t$ contains a totally odd immersion of $K_t$.

Immersion analogue of Hadwiger's conjecture. Every graph $G$ contains an immersion of $K_{\chi(G)}$.

Let $D$ be a digraph, let $k$ be a positive integer, and write $\delta^{+}(D)$ for its minimum out-degree. A transitive tournament on $k$ vertices is the tournament whose vertices…

Chromatic biclique immersion conjecture. If $1\leq \ell\leq \chi(G)-1$, then $G$ contains an immersion of $K_{\ell,\chi(G)-\ell}$.

Linear minimum out-degree conjecture. There exists an absolute constant $C>0$ such that for any positive integer $k$, every digraph $D$ satisfying