List-Labeling Equality for Trees

Definitions and mathematical statement

For a finite simple tree $T$, an $L(2,1)$-labeling is a function $f:V(T)\to{\mathbb{Z}}$ such that \[ |f(u)-f(v)|\ge2\quad\text{if }d_T(u,v)=1,\qquad |f(u)-f(v)|\ge1\quad\text{if }d_T(u,v)=2. \] Use $\chi^{2,1}(T)$ for the least $k\ge1$ admitting such a labeling with values in $\{1,\ldots,k\}$. Use $\chi^{2,1}_\ell(T)$ for the least $k$ such that, for every assignment of integer lists $L(v)$ with $|L(v)|=k$, there is an $L(2,1)$-labeling with $f(v)\in L(v)$ at every vertex.

The conjecture is \[ \forall\text{ trees }T,\qquad \chi^{2,1}_\ell(T)=\chi^{2,1}(T). \] The list inequality $\chi^{2,1}_\ell(T)\ge\chi^{2,1}(T)$ follows by taking identical consecutive lists; the requested direction is that the ordinary optimum suffices for every assignment of lists of that size, not just for a chosen list system.

The extract does not define its numerical normalization. The displayed convention counts consecutive available labels; a span convention instead counts maximum minus minimum and must use the corresponding one-unit list-size adjustment. Both sides must use the same source convention. The usual finite-tree setting is explicit here; no separate infinite-tree extension is asserted.

The literature assessment checked on 21 August 2026 records verification for stars, paths, comets and selected caterpillars, without a general all-trees solution. The cited later tree-labeling algorithm is not treated as a proof of the all-list-assignment assertion without checking its exact scope. This is supplied dated triage requiring independent verification.

Short English statement

For every tree, does the ordinary optimum for distance-one/two label separation suffice even when each vertex has an arbitrary list of that size? The source asks equality of list and ordinary labeling numbers, with their numerical conventions matched.

Sources

• Algorithmic Graph Theory (2006), Oberwolfach Reports, DOI 10.4171/owr/2006/07, pp. 379--460, https://doi.org/10.4171/owr/2006/07.
• Literature assessment checked 21 August 2026: original report, https://doi.org/10.4171/owr/2006/07; "later tree-labeling algorithm," https://arxiv.org/abs/0810.0906.
• Local UnsolvedMath registry, permanent ID $30000418$, exact source code catalogue entry, created 25 August 2026 and updated 16 September 2026. Supplied verification normalizes the tree and list-labeling equality without changing it.