58 problems

Hajós's conjecture. The graph $G$ contains a subdivision of $K_r$.

Let $D$ be a digraph, and let $f4a0$ be the minimum out-degree parameter. For a digraph $F$, define $mader_{\delta^+}(F)$ to be the least integer $m$ such that every digraph $D$ wi…

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$. Mader–Erdős–Hajnal conjecture. For $t\to\infty$,…

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…

Verstraëte's conjecture. For every graph $H$ and every $\eta>0$, there exists a threshold number $r_0$ such that every $n$-vertex, $r$-regular graph $G$ with $r\ge r_0$ contains a…

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…

A graph is a totally odd subdivision of $K_4$ if it is obtained from $K_4$ by replacing each edge with a path of odd length. Toft's conjecture. Every graph of chromatic number at l…

Spanning subdivision conjecture. For every $\varepsilon > 0$, there is a constant $C$ such that, for every graph $G$ on $n \geq Cm$ vertices with minimum degree at least

Let $t$ and $n$ be positive integers, and consider graphs on $n$ vertices with no $K_t$-subdivision. Clique-count conjecture. The maximum number of cliques in such a graph is … Thi…

Let $G$ be a graph, and let $G^{1/m}$ denote the graph obtained by replacing each edge of $G$ by a path of length $m$ through new vertices. A graph is locatable if a cop can guaran…

Let $t$ be a positive integer, and consider graphs containing no cycles of length $4$. Mader's conjecture. An average-degree condition only linear in $t$ is sufficient to force a s…

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 $G$ be a graph, let $s$ and $h$ be positive integers, and let $K_{s,s}$ and $K_h$ denote complete graphs. An induced $K_h$-subdivision is a subdivision of $K_h$ appearing as an…

Mader's threshold conjecture. The threshold $2s$ can be lowered to $s+1$.

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 $k$ and $\ell$ be positive integers. A $(k-1)$-subdivision of the in-star with $\ell$ leaves is obtained by replacing each edge of the in-star with $\ell$ leaves by a directed…

Let $G$ be an $(n,d,\lambda)$-graph, meaning that $G$ is a $d$-regular graph on $n$ vertices and every non-trivial eigenvalue of its adjacency matrix has absolute value at most…

Let $H$ and $G$ be graphs. A subdivision of $H$ is a graph obtained from $H$ by replacing edges with internally vertex-disjoint paths. An $H$-separating system of $G$ is a family o…

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 $G$ be a graph with $\omega(k^2)$ vertices, and suppose that $G$ has no small induced subgraph with almost the same average degree as the entire graph. Liu–Montgomery's conject…

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. The condition $d\ge \log n$ in Theorem could be totally dropped.

Let $H$ be a graph, and form subdivisions of $H$ by replacing its edges with internally vertex-disjoint paths. Consider subdivisions in which every subdivision path has length at l…