List-Labeling Numbers of Paths

Definitions and mathematical statement

The supplied conjectural equality is \[ \chi^{d,d}_{\ell}(P_n) =\left\lceil3d\left(1-\frac1n\right)\right\rceil+1. \] It is stated for every path $P_n$, with $d$ the repeated parameter of the source's $(d,d)$-list-labeling number. The ceiling is the least integer at least its argument; the final $+1$ lies outside it.

Under a common graph convention, $P_n$ has vertices $v_1,\ldots,v_n$ and edges $v_iv_{i+1}$ for $1\le i<n$. The source does not explicitly confirm whether $n$ counts vertices or edges, the admissible values of $d$, or exceptional small paths. The expression requires $n\ne0$, and positive integral separation parameters are a possible intended convention, not an explicit source hypothesis.

The invariant $\chi^{d,d}_{\ell}$ is not defined in the extraction. A common meaning of an $L(d,d)$ labeling uses integer labels with separation at least $d$ for adjacent vertices and for vertices at graph distance two, together with a prescribed list at each vertex. However, the source does not say whether its list-labeling number minimizes list cardinality, allowable label span plus one, a list-width parameter, or another quantity. It also omits the label universe, admissible lists, and whether the separation convention is exactly this one. None of these is silently selected: applying a familiar but different invariant could change the claimed formula and its small-parameter cases.

Thus the task is to establish or refute the displayed exact equality for the report's invariant, with the report's full quantifiers and conventions recovered. The equality is not weakened to an upper bound or an asymptotic formula. The supplied connection to precoloring-extension bounds is contextual and does not identify a theorem proving this exact list-labeling statement.

Short English statement

The source proposes an exact ceiling formula for the $(d,d)$-list-labeling number of a path. The invariant, parameter range, path indexing, and list conventions are not supplied, so these must be recovered before the formula becomes a precise claim.

Sources

• Local UnsolvedMath registry, permanent ID 30000417, source code catalogue entry, "List-Labeling Numbers of Paths." Proposed year 2006; proposer unspecified.
• Algorithmic Graph Theory (2006), Oberwolfach Reports, pp. 379--460, DOI 10.4171/owr/2006/07; https://doi.org/10.4171/owr/2006/07.
• Supplied reference "Hutchinson and Moore": https://doi.org/10.1016/j.jctb.2006.08.003.
• Statement status corrected_verified; the supplied note says path, parameter, list-labeling, and ceiling notation were restored without changing the quantifier or equality. It supplies no invariant definition.
• Literature triage checked 2026-08-21: partially solved. It reports later optimal distance bounds for broad precoloring-extension settings covering substantial related cases, while saying the extracted list-coloring conjecture is not fully identified as one general theorem. Exact correspondence and current status require independent verification. Created 2026-08-25; updated 2026-09-16.
• Registry curation by Ulam AI / UnsolvedMath Contributors, CC BY 4.0; underlying report and literature provenance remain as supplied. Unreviewed statement-only draft.