19 problems

Dobson's conjecture. If

Let $c>0$, let $K$ be sufficiently large depending on $c$, let $G$ be a graph on $n$ vertices with average degree $d$, and let $T$ be a tree on $(1-c)d$ vertices with maximum degre…

Let $c$ satisfy $1/2<c\leqslant1$, and let $G$ be an $n$-vertex graph with minimum degree $\delta(G)\geqslant cn$. Colourful tree embedding conjecture. There exists a constant…

Let $\mathcal{C}$ be a hereditary class of finite graphs. Assume the dichotomy under consideration is the alternative that $\mathcal{C}$ is not $2$-well-quasi-ordered or that its i…

Let $k$ be a positive integer. For a graph $G$ and a vertex $x\in V(G)$, let $N_G(x)$ be the neighbourhood of $x$, and let $N_G^2(x)$ be the set of vertices other than $x$ sharing…

Let $\ell$ and $k$ be positive integers, let $G$ be a graph, and let $T$ be a tree with $k$ edges. Write $\delta(G)$ and $\Delta(G)$ for the minimum and maximum degrees of $G$, and…

Let $D$ be a digraph, let $k$ be a positive integer, and let … delta^0(D)=min{vin V(D)}min{d^+(v),d^-(v)} … … contains each oriented path with $k$ edges. This is presented as a pos…

Exact bipartite Komlós–Sárközy–Szemerédi conjecture. For each $\gamma>0$, there are $c,n_0>0$ such that for every $n\ge n_0$, if $G=(A,B,E)$ is a balanced bipartite graph on $2n$ v…

Let $T$ be an antidirected tree, meaning an oriented tree without a directed path of length two. Then there is a constant $c_T$ such that every sufficiently large directed graph…

Let $T$ be a tree on at most $(1-\varepsilon)n$ vertices with maximum degree at most $d$, where $\varepsilon\in(0,1)$ and $d\geq 2$ is an integer. Consider a uniformly coloured ran…

Let $T$ be a complete balanced binary tree, and let $S$ be a rooted tree. Write $g_T(S)$ for the number of good embeddings of $S$ into $T$, and $a_T(S)$ for the number of all embed…

Let $m\in\mathbb N$. A graph $G$ has maximum degree at least $m$ and minimum degree at least $\lfloor \frac{2m}{3} \rfloor$. A spanning-tree embedding conjecture. Under these condi…

Let $k\in\mathbb{N}$, and let $G$ be a graph. For a vertex $x\in V(G)$, let $N(x)$ denote its neighbourhood and let $N_2(x)$ denote its second neighbourhood. Large first- and secon…

Let $k\in\mathbb{N}$, let $0\leq\alpha\leq \frac{1}{2}$, and let $G$ be a graph. Write $\delta(G)$ and $\Delta(G)$ for the minimum and maximum degrees of $G$, respectively. Interpo…

Let $k,\Delta\in\mathbb{N}$, and let $G$ be a graph. Write $\delta(G)$ and $\Delta(G)$ for the minimum and maximum degrees of $G$, respectively. Constant-degree-tree conjecture. If…

Let $k\in\mathbb{N}$, and let $G$ be a graph. A tree with $k$ edges is a tree having $k+1$ vertices. The $2k$–$\frac{k}{2}$ conjecture. If … then $G$ contains every tree with $k$ e…

Let $G$ be a graph and let $T$ be a tree with $m$ edges. Variant of the Erdős–Sós conjecture. If $G$ has maximum degree at least $m$ and minimum degree at least … then $G$ contains…

Let $G$ be a graph on $n$ vertices, and let $k$ be a positive integer. A tree with $k$ edges has $k+1$ vertices. Komlós–Sós conjecture. If at least $n/2$ vertices of $G$ have degre…

Let $G$ be a graph on $n$ vertices. A tree has at most $n/2$ edges when its size is at most $n/2$. Loebl's $(n/2-n/2-n/2)$ conjecture. Any graph on $n$ vertices with at least $n/2$…