Further results on minimal rankings. (English) Zbl 0977.05048

A \(k\)-ranking of a graph is a coloring of its vertices by integers from \(\{1,2,\dots ,k\}\) such that for any two vertices colored by the same color, each path connecting these two vertices contains a vertex colored by a higher color. A \(k\)-ranking is minimal if recoloring any single vertex by a lower color results in a coloring which is no more a ranking. The authors continue their study of minimal rankings initiated in [Networks 28, No. 1, 45-53 (1996; Zbl 0863.05071)]. In particular they present a paradigm for constructing minimal rankings of arbitrary graphs, they show several bounds on the rank and \(k\)-rank (a related graph invariant) of a number of graphs. The bounds involve the independence number, the size of maximum matching and the size of maximum induced matching. They also show that for some classes of graphs (\(2K_2\)-free graphs, connected cographs) some of these bounds become equalities.


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


Zbl 0863.05071