Extremal results in rankings. (English) Zbl 0989.05058

Laskar, R.; Pillone, D.

Congr. Numerantium 149, 33-54 (2001).

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.

Reviewer: Haiko Müller (Leeds)

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

Citations:

Zbl 0977.05048