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.


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


Zbl 0977.05048