1. On the Nash number and the diminishing Grundy number of a graph
- Author
-
Frédéric Havet, Allen Ibiapina, Leonardo Rocha, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Universidade Federal do Ceará = Federal University of Ceará (UFC), and State University of Ceara / Universidade Estadual do Ceara (UECE)
- Subjects
Applied Mathematics ,Grundy colouring ,Discrete Mathematics and Combinatorics ,Complexity ,Colouring parameters ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Colouring ,Game theory - Abstract
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}
- Published
- 2022
- Full Text
- View/download PDF