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

From papers

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.

Progress summary

Open

No publicly verified progress was found on the conjectured upper bound for chains of trees.

The conjecture concerns the independence-polynomial order on trees and asserts that every chain on $n$ vertices has at most $n-2$ elements. The supplied paper reportedly constructs a chain attaining this bound, but no retrieved source documents a proof, counterexample, or subsequent verification.

Current status (as of August 2026): The conjecture remains open on the retrieved evidence; the bound is attained by an exhibited chain, but no longer-chain obstruction or counterexample is publicly verified.

Sources & referencesView supporting material

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

1 week ago

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.

0 endorsements

Shivam Patel · 1 day ago