Coloring parameters associated with rankings of graphs. (English) Zbl 1043.05049

A ranking of a graph is a function that assigns to each vertex a positive integer such that any path between two vertices with the same rank has a vertex of higher rank. In a co-ranking, this must be a vertex of smaller rank. A bi-ranking is both a ranking and a co-ranking. With each of these types of graph labelings, one can associate graph parameters, like the minimum number of values needed for a ranking/co-ranking/bi-ranking. The paper surveys existing results and gives new results including upper and lower bounds on these parameters.


05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)