Sublinear polynomial upper bound for the on-line ranking number of trees

Let TT be an nn-vertex tree with maximum degree kk, and let ρ˚(T)\mathring{\rho}(T) denote its on-line ranking number.

On-line ranking conjecture. There exist universal constants aa and bb satisfying 0<a<1<b0<a<1<b such that

ρ˚(T)b(kn)a.\mathring{\rho}(T)\leq b(kn)^a.

This conjecture proposes a general upper bound for the on-line ranking number of trees, analogous to the bounds established for the trees Tk,dT_{k,d} in the paper. The supplied context does not state whether the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Daniel C. McDonald, “On-line vertex ranking of trees”, arXiv:1401.2669 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.