282 problems

Coefficient formula conjecture. The coefficient of $x^{2n-5}$ is

Tree equidistant dimension conjecture.

Let $G$ be a tree on $n\geq 2$ vertices. Write $E_{\mathrm{ISI}}(G)$ for its inverse sum indegree energy, and let $S_n$ and $P_n$ denote the star and path on $n$ vertices, respecti…

Let $\mathcal{T}_n$ be the set of all trees with $n$ vertices, ordered by $\succeq$. The length of a chain is the number of elements in a sequence $T_1\succ T_2\succ\cdots$ under t…

Parity conjecture for trees. The Grundy value of a tree is zero if and only if its size is even.

Let $T$ be a tree of order $n\geq 3$. For a graph $G$ of order $n$, write $\delta_k(G)$ for the coefficients of its distance characteristic polynomial and define the normalized coe…

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.…

Tree upper-bound conjecture. If $3 \leq p \leq d$, then

Let $F$ be a tree of order $\ell\geq 4$. For integers $n,k,p$ with $n>k>0$ and $p\in\{0,\dots,\lfloor(n-k)/2\rfloor\}$, let $S_{n,k}^{p}$ be the graph obtained from…

Barát–Thomassen conjecture. For every tree $T$, there exists a positive integer $k_T$ such that every $k_T$-edge-connected simple graph whose size is divisible by $|E(T)|$ admits a…

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…

Mader's conjecture. For any tree $\T$ of order $\m$, every $\k$-connected graph $\G$ with minimum degree

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…

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$.

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 $G$ be a finite tree, and let $\widetilde{\chi}_G^{\mathbf{1}}(q,x)$ denote the $q$-chromatic polynomial of $G$ with respect to the all-ones weight vector $\mathbf{1}$. Leading…

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…

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

Graham–Sloane conjecture. Every tree is harmonious.

An odd-graceful labeling is the tree-labeling notion in which the edge labels are the required distinct odd values. Odd-graceful tree conjecture. Every tree admits an odd-graceful…

Let $G$ and $H$ be non-isomorphic graphs. We call $H$ a twin of $G$ if there are embeddings $G\to H$ and $H\to G$, that is, injective maps $V(G)\to V(H)$ and $V(H)\to V(G)$ preserv…

Henning–Oellermann–Swart conjecture.

For $k\ge 1$, let $T$ be a tree of order $m$, and let $G$ be a $k$-connected or $k$-edge-connected graph with minimum degree $\delta(G)\ge k+m-1$. A subtree $T'$ is isomorphic to…

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.…