On the properties of weighted minimum colouring games

Research output: Contribution to journalJournal articleResearchpeer-review

  • Herbert Hamers
  • Nayat Horozoglu
  • Henk Norde
  • Trine Tornøe Platz

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, (2 K2, P4) -free). Finally, we show that G is globally PMAS-admissible if and only if it is (2 K2, P4) -free, and we provide a partial characterisation of locally PMAS-admissible graphs.

Original languageEnglish
JournalAnnals of Operations Research
Volume318
Pages (from-to)963–983
Number of pages21
ISSN0254-5330
DOIs
Publication statusPublished - 2022

Bibliographical note

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

    Research areas

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

ID: 300444574