On the Nash number and the diminishing Grundy number of a graph
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.
- A Game Theoretic Approach for Efficient Graph Coloring
- A short proof that can be bounded away from + 1 toward
- Graph theory
- Grundy number and products of graphs
- scientific article; zbMATH DE number 1286500 (Why is no real title available?)
- scientific article; zbMATH DE number 3800939 (Why is no real title available?)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- On the list coloring version of Reed's conjecture
- On-line and first fit colorings of graphs
- Reducibility among combinatorial problems
- Results on the Grundy chromatic number of graphs
- Strategic coloring of a graph
- Sur le coloriage des graphs
- The NP-Completeness of Edge-Coloring
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
This page was built for publication: On the Nash number and the diminishing Grundy number of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2127607)
