Originators: Robert Jamison (presented by Robert Jamison - REGS 2011)
Definitions: For a graph G, a coloring f: V(G)→{1,2,...,k} is a k-ranking if every path whose endpoints have the same rank contains a vertex with higher rank. The ranking number r(G) is the minimum k such that G has a k-ranking. Note that every ranking is a proper coloring, so r(G)≥χ(G).
A list assignment on a graph G is a function L that assigns to each vertex v a finite set L(v) of positive integers. The set L(v) is the list of v. Think of L(v) as a "palette of colors" available for use at v. Given a list assignment L on G, an L-ranking is a ranking f of G such that f(v)∈L(v) for all v∈V(G). The list rank number or rank choice number h(G) is the least k such that G has an L-ranking whenever L is a list assignment in which all lists have size at least k.
Background: The definitions for list ranking are analogous to list coloring, and thus the list rank number could also be called the "rankability", by analogy with "choosability". By iteratively choosing colors not yet used, it is immediate that the rank choice number of G is well defined and always at most |V(G)|, since when the colors at vertices are distinct the path condition vacuously holds.
[J] is a survey of rankings through 2003. More recent papers by Darren Narayan with various coauthors have studied k-rankings, minimal rankings, aranking, and biranking. The studied of rankings is motivated by applications to VLSI layout ([IRV]), Cholesky factorization ([KMW]), computational geometry ([E]), etc.
Question 1: For which trees does the list ranking number equal the ranking number? In particular, is this true for all paths?
Question 2: For any tree, the list ranking number is at least the number of leaves. When does equality hold?
Question 3: For any nontrivial tree, the list ranking number is less than the number of vertices. Does equality hold for any trees other than stars?
Question 4: What are the best bounds on the list ranking number in terms of the maximum degree? Is there a bound on the list ranking number in terms of the ranking number?
References:
[E] J. Erickson et al.
[J] Robert E. Jamison,
Coloring parameters associated with rankings of graphs,
Congr. Numer. 164(2003), 111--127.
[IRV] Iyer, Ratliff, and Vijayan, 1988.
[KMW] Kloks, Mulder, and Wong, 1998.