## Extremal results in rankings.(English)Zbl 0989.05058

A $$k$$-ranking of a graph $$G$$ is a colouring of its vertices by integers from $$\{1,2,\dots,k\}$$ such that each path with endpoints coloured by the same integer contains an internal vertex coloured by a greater integer. A $$k$$-ranking is minimal if recolouring any single vertex by a lesser integer results in a colouring which is not a ranking any more. The numbers $$\chi_{\text{r}}(G)$$ and $$\psi_{\text{r}}(G)$$ denote the minimum and maximum value of $$k$$ such that $$G$$ has a minimal $$k$$-ranking, see J. Ghoshal, R. Laskar, and D. Pillone [Ars Comb. 52, 181-198 (1999; Zbl 0977.05048)]. This paper considers the minimum and maximum number of edges in a graph $$G$$ with a given number of vertices and fixed values of $$\chi_{\text{r}}(G)$$ and $$\psi_{\text{r}}(G)$$, respectively.

### MSC:

 05C35 Extremal problems in graph theory 05C15 Coloring of graphs and hypergraphs 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

### Keywords:

vertex ranking; minimal ranking; rank number; colouring

Zbl 0977.05048