Let 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… under this order. Chain-length conjecture. The length of every chain in (T_n,succeq) is at most n-2. The paper exhibits a chain of length n-2 and conjectures that no longer chain exists, while also observing that trees with the same maximum degree can be comparable.

The chain-length conjecture for the independence-polynomial order on trees

About 13 years old · traced to 2013

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 this order. Chain-length conjecture. The length of every chain in $(\mathcal{T}_n,\succeq)$ is at most $n-2$ . The paper exhibits a chain of length $n-2$ and conjectures that no longer chain exists, while also observing that trees with the same maximum degree can be comparable.

References

Primary source

Mohammad Reza Oboudi, “On the largest real root of independence polynomials of graphs, an ordering on graphs, and starlike trees”, arXiv:1303.3222 (2013).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader-written construction claims the conjecture is false at 15 vertices, but nobody has independently verified it.

Oboudi’s paper formulates the upper bound of $n-2$ for chains in the independence-polynomial order on trees and exhibits a chain attaining that bound.

Known results

Oboudi, 2013: $S_n\succeq T\succeq P_n$ for every tree $T$ of order $n$ .
Oboudi, 2013: strict majorization of branch-length tuples implies strict comparison of the corresponding starlike trees.
Oboudi, 2013: trees with equal maximum degree can nevertheless be comparable.

Posted attempt

A posted construction gives fourteen distinct $15$ -vertex starlike trees whose branch-length tuples form a strict majorization chain. It therefore claims a chain of length $14$ , exceeding the conjectured bound $15-2=13$ ; the attempt has not been independently verified.

Current status (as of August 2026): the bound is attained by the paper’s exhibited chain, while a $15$ -vertex violation is only an unverified posted claim.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

The conjecture is false already for trees on 15 vertices. Let $T(a_1,\ldots,a_5)$ denote the starlike tree obtained by identifying one endpoint of five paths having $a_1,\ldots,a_5$ vertices. Thus its order is $a_1+\cdots+a_5-4$ . Consider, in the displayed order, the following five-tuples:

\begin{gathered} (11,2,2,2,2),\ (10,3,2,2,2),\ (9,4,2,2,2),\\ (9,3,3,2,2),\ (8,4,3,2,2),\ (7,5,3,2,2),\\ (7,4,4,2,2),\ (7,4,3,3,2),\ (6,5,3,3,2),\\ (6,4,4,3,2),\ (6,4,3,3,3),\ (5,5,3,3,3),\\ (5,4,4,3,3),\ (4,4,4,4,3). \end{gathered}

Each tuple is nonincreasing, has entries at least 2, and has sum 19. Hence all fourteen corresponding trees have order $19-5+1=15$ and maximum degree 5. For each pair of consecutive tuples $a,b$ , the partial sums satisfy

\sum_{i=1}^j a_i\geq\sum_{i=1}^j b_i \qquad(1\leq j\leq5),

with strict inequality for at least one $j$ ; thus $a$ strictly majorizes $b$ . Theorem 14 of the source paper therefore gives $T(b)\succ T(a)$ in precisely the strict independence-polynomial order appearing in the conjecture. The branch multisets are distinct, so the fourteen starlike trees are pairwise nonisomorphic. Reversing the displayed order produces a strict chain of fourteen distinct 15-vertex trees.

The source explicitly defines the length of a chain to be its number of elements. The conjectured upper bound at $n=15$ is $n-2=13$ , whereas this chain has length 14. Therefore the conjecture is false.