On the properties of weighted minimum colouring games
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
On the properties of weighted minimum colouring games. / Hamers, Herbert; Horozoglu, Nayat; Norde, Henk; Platz, Trine Tornøe.
In: Annals of Operations Research, Vol. 318, 2022, p. 963–983.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - On the properties of weighted minimum colouring games
AU - Hamers, Herbert
AU - Horozoglu, Nayat
AU - Norde, Henk
AU - Platz, Trine Tornøe
N1 - Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - (2 K
KW - Complete multipartite graph
KW - P) -free graph
KW - Population monotonic allocation schemes
KW - Submodularity
KW - Totally balancedness
KW - Weighted minimum colouring game
U2 - 10.1007/s10479-021-04374-9
DO - 10.1007/s10479-021-04374-9
M3 - Journal article
AN - SCOPUS:85124716717
VL - 318
SP - 963
EP - 983
JO - Annals of Operations Research
JF - Annals of Operations Research
SN - 0254-5330
ER -
ID: 300444574