On the Nash number and the diminishing Grundy number of a graph (Q2127607): Difference between revisions

The paper investigates properties of a graph colouring parameter introduced by \textit{P. N. Panagopoulou} and \textit{P. G. Spirakis} [Lect. Notes Comput. Sci. 5369, 183--195 (2008; Zbl 1183.68585)] which is inspired by game-theoretic considerations. The closely related concept of `diminishing greedy colourings' is also studied. A Nash \(k\)-colouring of a graph \(G\) is a vertex partition into \(k\) sets \(\{S_1, \dotsc, S_k\}\) such that, if \(|S_i| \leq |S_j|\), then every vertex in \(S_i\) has a neighbour in \(S_j\) (this type of colouring corresponds to a `Nash equilibrium' of a certain type of games defined on graphs, and hence the name). The Nash number \(\operatorname{Nn}(G)\) of a graph \(G\) is the maximum \(k\) such that \(G\) admits a Nash \(k\)-colouring. A diminishing greedy \(k\)-colouring of a graph \(G\) is a vertex partition into \(k\) sets \(\{S_1, \dotsc, S_k\}\) such that, for every \(i < j\), \(|S_i| \geq |S_j|\) and every vertex in \(S_j\) has a neighbour in \(S_i\) (note that the difference with Nash \(k\)-colourings is that here for two different sets with \(|S_i| = |S_j|\) have no extra requirement, whereas for Nash \(k\)-colourings the vertices in \(S_i\) are required to have neighbours in \(S_j\) and vice versa). The diminishing Grundy number \(\Gamma^\downarrow(G)\) is the maximum \(k\) such that \(G\) has a diminishing greedy \(k\)-colouring. The results of the paper can be summarised in four main types: 1.) The parameters \(\operatorname{Nn}(G)\) and \(\Gamma^\downarrow(G)\) are bounded from above and below using more usual graph colouring parameters, such as the clique number, chromatic number, Grundy number, maximum degree. As an example, the bound \(\operatorname{Nn}(G) \leq \Gamma^\downarrow(G)\) holds, but the bound \(\Gamma^\downarrow(G)\) cannot be bounded from above by any function of \(\operatorname{Nn}(G)\). 2.) Bounds in the style of \textit{B. Reed}'s result [J. Graph Theory 27, No. 4, 177--212 (1998; Zbl 0980.05026)] that the chromatic number can be bounded from above by a non-trivial convex combination of the clique number and the maximum degree, but replacing the parameters in this formula with \(\operatorname{Nn}(G)\) and \(\Gamma^\downarrow(G)\). 3.) \(\operatorname{Nn}(G)\) and \(\Gamma^\downarrow(G)\) for trees and forests. 4. Complexity results for \(\operatorname{Nn}(G)\) and \(\Gamma^\downarrow(G)\): both are NP-hard to compute, even when restricted to bipartite or chordal graphs.