511 problems

Let $T$ be a tree on $t$ vertices. For a graph $G$, write $e(G)$ for its number of edges, and call $G$ $T$-free if it contains no subgraph isomorphic to $T$. Erdős–Sós conjecture.…

For $k\ge 1$ and any tree $T$ of order $m$, let $G$ be a $k$-connected graph with minimum degree $delta(G)\ge \left\lfloor 3k/2\right\rfloor+m-1$. A subtree $T'$ is isomorphic to…

Let $T$ be an oriented tree on $n$ vertices, and let $\vv{r}(T)$ be the least $N$ such that every tournament on $N$ vertices contains a copy of $T$. Sumner's conjecture. … This is…

A tree is a connected graph with no cycles, and a labelling of a graph with $m$ edges is an injective map from its vertices to the positive integers. Such a labelling is graceful i…

Hovey's cordial labelling conjecture. Every tree admits a labelling by $\mathbb{Z}_k$, for every $k$, such that each vertex label occurs either $s$ or $s+1$ times and each edge lab…

Loebl–Komlós–Sós conjecture. If at least $n/2$ vertices of $G$ have degree at least $d$, then $G$ contains a copy of $T$.

Let $T$ be a tree with vertex set $V(T)$ and edge set $E(T)$, and let $n=|V(T)|$. A graceful labeling of $T$ is a bijection … such that the induced edge labels are exactly…

Graham–Sloane conjecture. Every tree is harmonious.

Erdős–Palka conjecture. For every $C>1$, with high probability $G(n,C/n)$ contains an induced tree of linear size.

For an $n$-vertex graph, the $m$-deck is the multiset of its unlabeled induced $m$-vertex subgraphs, and a family of graphs is weakly $celltext{ell}$-reconstructible if no two grap…

Graham–Häggkvist conjecture. The edge set of $K_{n,n}$ can be decomposed into copies of every $n$-edge tree $T$.

Gronau–Mullin–Rosa conjecture. For every $n$-vertex tree $T$ other than the path on $4$ vertices, $K_n$ has an orthogonal double cover by copies of $T$.

Let $T$ be a tree with $n$ vertices. For $0\leq k\leq n-2$, let $d_k(T)$ denote the normalized coefficient of degree $k$ in the distance characteristic polynomial of $T$. A sequenc…

Friedman's conjecture. A Faber–Krahn type inequality should hold for regular trees with given volume.

For a graph $G$, define its Laplacian energy by … where $L(G)$ is the Laplacian matrix and $\lambda_i(L(G))$ are its eigenvalues. Let $P_n$ be the path on $n$ vertices. Radenković–…

Let $G$ and $H$ be trees, and let $\chi_G(x)$ denote the chromatic symmetric function of $G$. Tree isomorphism conjecture. If $G$ and $H$ are non-isomorphic trees, then … The conje…

Let $T$ be a tree, let $k\geq 1$, and let $\mathcal{I}_{T}^{k}(v)$ denote the family of independent sets of size $k$ in $T$ containing $v$. A leaf-centred maximum-star conjecture.…

Let $G$ be a connected graph of order $n$. The burning number $b(G)$ is the minimum length of a burning sequence for $G$, where a burning sequence is a sequence of sources that pro…

Let $G=(V,E)$ be a finite tree. Its generalized degree polynomial (GDP) is … where $\operatorname{ext}(A)$ is the number of edges of $E$ with one endpoint in $A$, and…

An oriented graph $G$ on $n$ vertices has an edge for each oriented edge of its underlying graph. An antidirected tree is an orientation of a tree in which every vertex has either…

A series-reduced tree is a tree with no vertex of degree $2$, and its average order of a subtree is the mean number of vertices over all subtrees of the tree. Jamison's conjecture.…

Let $T$ be a tree with order $n$ and diameter $\operatorname{diam}(T)$, and let $md(T)$ denote its multiset dimension. Hafidh's conjecture. If $md(T)<\infty$, then … and this bound…

The strengthened burning number conjecture. The tree $T$ is $m$-burnable.

Let $T_1$ and $T_2$ be trees of order at least $2$, and let $\gamma_{\mathrm{pr}}(T)$ denote the paired domination number of a graph $T$. Strict paired domination conjecture. … The…

Let the frog model start with one frog per vertex on the homogeneous tree $\mathbb{T}_d$ of degree $(d+1)$, with frogs performing the model's random walks and waking sleeping frogs…