31 problems

A proper edge-colouring is one in which incident edges receive distinct colours, and a rainbow $K_k$-subdivision is a subdivision of $K_k$ whose edges have pairwise distinct colour…

Let $d(t)$ be the smallest real number such that every graph with average degree more than $d(t)$ contains a subdivision of $K_t$. Kühn–Osthus lower-bound conjecture. As…

Let $F$ be an acyclic digraph, and let $\delta^+(D)$ denote the minimum out-degree of a digraph $D$. A subdivision of $F$ is obtained by replacing the arcs of $F$ by directed paths…

Given a graph $H$ and a function $c3:E(H)\to\mathbb{N}$, the subdivision $H^{\sigma}$ is obtained by replacing each edge $e\in E(H)$ with a path of length $\sigma(e)$. For a graph…

Given graphs $F$ and $G$, a subdivision packing of $F$ in $G$ is a collection of pairwise vertex-disjoint copies of subdivisions of $F$. For a real number $\eta > 0$ and a graph…

Let $H$ be a graph with at least one edge. A subdivision of $H$ is obtained by replacing edges of $H$ with pairwise internally vertex-disjoint paths; let $\operatorname{Sub}(H)$ be…

Fix $d\in\mathbb{N}$ and let $H$ be a graph of maximum degree $3$. Let $k\in\mathbb{N}$, and let $G$ be an $(=\hspace{-0.2em}k,d)$-vertex expander, meaning that every set…

Let $G$ be a graph, let $d(G)$ denote its average degree, and let a balanced $K_t$-subdivision be a subdivision of $K_t$ in which all subdivided edge-paths have the same length. Th…

Let $t$ be a positive integer. An orientation of the cycle on $t$ vertices is obtained by assigning a direction to each edge of that cycle. Common degree conjecture. Every digraph…

Let $H$ be a planar maximal 3-degenerate graph. A subdivision of $H$ is a graph obtained by replacing edges by internally vertex-disjoint paths. Diwan's conjecture. Every graph wit…

Let $F$ be a digraph, and let $\mathrm{mader}_{\vec{\chi}}(F)$ be the least integer $k$ such that every digraph $D$ with dichromatic number $\vec{\chi}(D)\geq k$ contains a subdivi…

Spanning subdivision conjecture. If

Given a graph $H$ and an integer $\ell$, a balanced $H$-subdivision is obtained by replacing every edge of $H$ with an internally vertex-disjoint path of length $\ell$, denoted…

A balanced subdivision of a graph $H$ is obtained by replacing every edge of $H$ with an internally vertex-disjoint path of the same length; write this as $TH^{(\ell)}$ when that l…

Secure-domination lower-bound conjecture. For every graph $G$,

Let $T_k$ be the transitive tournament on $k$ vertices, and let $H_k$ be its $1$-subdivision, obtained by subdividing every arc exactly once. For an oriented graph $H$, let…

Let $G$ be a graph, let $k$ be an integer, and let $G'$ be any $(\leqslant k)$-subdivision of $G$, obtained by replacing each edge of $G$ by an internally disjoint path with at mos…

Out-leaf extension conjecture. The digraph $F^\ast$ is $\delta^+$-maderian as well.

Long-subdivision extraction conjecture. There is a function $f:\mathbb{N}\rightarrow\mathbb{N}$ such that for every $k\in\mathbb{N}$ and every digraph $D$ with

Subdivision-preservation conjecture. If a digraph $F$ is $\delta^+$-maderian, all subdivisions of $F$ are $\delta^+$-maderian as well.

Aboulker et al.'s cycle-orientation conjecture. Every orientation of a cycle is $\delta^+$-maderian.

Mader's forest-orientation conjecture. Every orientation of a forest is $\delta^+$-maderian.

Planar maximal 3-degenerate graph conjecture. Every planar maximal 3-degenerate graph is good.

Admissible-subgraph density conjecture. If $(Q,\phi)$ has no $H$-admissible subgraph for any $H\in\mathcal{H}$, then

Subdivision conjecture. If the minimum degree of $G$ is at least $n/2-k+1$, then $G$ contains a subdivision of $H$.