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

Hamers, H, Horozoglu, N, Norde, H & Platz, TT 2022, 'On the properties of weighted minimum colouring games', Annals of Operations Research, vol. 318, pp. 963–983. https://doi.org/10.1007/s10479-021-04374-9

APA

Hamers, H., Horozoglu, N., Norde, H., & Platz, T. T. (2022). On the properties of weighted minimum colouring games. Annals of Operations Research, 318, 963–983. https://doi.org/10.1007/s10479-021-04374-9

Vancouver

Hamers H, Horozoglu N, Norde H, Platz TT. On the properties of weighted minimum colouring games. Annals of Operations Research. 2022;318:963–983. https://doi.org/10.1007/s10479-021-04374-9

Author

Hamers, Herbert ; Horozoglu, Nayat ; Norde, Henk ; Platz, Trine Tornøe. / On the properties of weighted minimum colouring games. In: Annals of Operations Research. 2022 ; Vol. 318. pp. 963–983.

Bibtex

@article{6bd9406ad6454d9a86acd9a5ecb9d209,
title = "On the properties of weighted minimum colouring games",
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, (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.",
keywords = "(2 K, Complete multipartite graph, P) -free graph, Population monotonic allocation schemes, Submodularity, Totally balancedness, Weighted minimum colouring game",
author = "Herbert Hamers and Nayat Horozoglu and Henk Norde and Platz, {Trine Torn{\o}e}",
note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",
year = "2022",
doi = "10.1007/s10479-021-04374-9",
language = "English",
volume = "318",
pages = "963–983",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer",

}

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