On the properties of weighted minimum colouring games

Herbert Hamers, Nayat Horozoglu, Henk Norde, Trine Tornoe Platz*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

64 Downloads (Pure)

Abstract

A weighted minimum colouring (WMC) game is induced by an undirected graph and a positive weight vector on its vertices. The value of a coalition in a WMC game is determined by the weighted chromatic number of its induced subgraph. A graph G is said to be globally (respectively, locally) WMC totally balanced, submodular, or PMAS-admissible, if for all positive integer weight vectors (respectively, for at least one positive integer weight vector), the corresponding WMC game is totally balanced, submodular or admits a population monotonic allocation scheme (PMAS). We show that a graph G is globally WMC totally balanced if and only if it is perfect, whereas any graph G is locally WMC totally balanced. Furthermore, G is globally (respectively, locally) WMC submodular if and only if it is complete multipartite (respectively, (2K(2), P-4)-free). Finally, we show that G is globally PMAS-admissible if and only if it is (2K(2), P-4)-free, and we provide a partial characterisation of locally PMAS-admissible graphs.
Original languageEnglish
Pages (from-to)963-983
JournalAnnals of Operations Research
Volume318
DOIs
Publication statusPublished - Nov 2022

Keywords

  • Weighted minimum colouring game
  • Totally balancedness
  • Submodularity
  • Population monotonic allocation schemes
  • Complete multipartite graph
  • (2K(2), P-4)-free graph
  • ALGORITHM
  • GRAPHS

Fingerprint

Dive into the research topics of 'On the properties of weighted minimum colouring games'. Together they form a unique fingerprint.

Cite this