## 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.

### MSC:

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

### Keywords:

coloring; ranking; chordal graph; cograph

Zbl 0863.05071