On the Nash number and the diminishing Grundy number of a graph

International audience; A Nash k-colouring is a k-colouring (S1, . . . , Sk) such that every vertex of Si is adjacent to a vertex in Sj, whenever |Sj| ≥ |Si|. The Nash Number of G, denoted by Nn(G), is the largest k such that G admits a Nash k-colouring. A diminishing greedy k-colouring is a k-colouring (S1, . . . , Sk) such that, for all 1 ≤ j < i ≤ k, |Si| ≤ |Sj| and every vertex of Si is adjacent to a vertex in Sj. The diminishing Grundy Number of G, denoted by Γ ↓(G), is the largest k such that G admits a diminishing greedy k-colouring. In this paper, we prove some properties of Nn and Γ ↓. We mainly study the relations between them and other graph parameters such as the clique number ω, the chromatic number χ , the Grundy number Γ , and the maximum degree ∆. In particular we study the chain of inequalities ω(G) ≤ χ(G) ≤ Nn(G) ≤ Γ ↓(G) ≤ Γ (G) ≤ ∆(G)+1. We show each inequality γ1(G) ≤ γ2(G) of this chain is loose, in the sense that there is no function f such that γ2(G) ≤ f (γ1(G)). We also prove the existence or non-existence of inequalities analogue to Reed’s one stating that there exists ε > 0 such that χ (G) ≤ εω(G) + (1 − ε)(∆(G) + 1).We then study the Nash number and the diminishing Grundy number of trees and forests, and prove that Γ (F ) − 1 ≤ Nn(F ) ≤ Γ ↓(F ) ≤ Γ (F ).Finally we study the complexity of related problems. We show that computing the Nash number or the diminishing Grundy number is NP-hard even when the input graph is bipartite or chordal. We also show that deciding whether a graph satisfies γ1(G) = γ2(G) is NP-hard for every pair (γ1, γ2) with γ1 ∈ {Nn, Γ ↓} and γ2 ∈ {ω, χ , Γ , ∆ + 1}