Simple and three-valued simple coloring games

Marieke Musegaas, Peter Borm, Marieke Quant

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper minimum coloring games are considered. We characterize the class of conflict graphs inducing simple or three-valued simple minimum coloring games. We provide an upper bound on the number of maximum cliques of conflict graphs inducing such games. Moreover, a characterization of the core is provided in terms of the underlying conflict graph. In particular, in case of a perfect conflict graph the core of an induced three-valued simple minimum coloring game equals the vital core.
Original languageEnglish
Pages (from-to)239-258
Number of pages20
JournalMathematical Methods of Operations Research
Volume84
Issue number2
DOIs
Publication statusPublished - Oct 2016

Fingerprint

Coloring
Colouring
Game
Graph in graph theory
Maximum Clique
Simple Graph
Upper bound
Conflict
Graph

Keywords

  • minimum coloring games
  • simple games
  • three-valued simple games

Cite this

@article{ddeab4bd6c2748a99cecf35f50be8e6f,
title = "Simple and three-valued simple coloring games",
abstract = "In this paper minimum coloring games are considered. We characterize the class of conflict graphs inducing simple or three-valued simple minimum coloring games. We provide an upper bound on the number of maximum cliques of conflict graphs inducing such games. Moreover, a characterization of the core is provided in terms of the underlying conflict graph. In particular, in case of a perfect conflict graph the core of an induced three-valued simple minimum coloring game equals the vital core.",
keywords = "minimum coloring games, simple games, three-valued simple games",
author = "Marieke Musegaas and Peter Borm and Marieke Quant",
year = "2016",
month = "10",
doi = "10.1007/s00186-016-0542-4",
language = "English",
volume = "84",
pages = "239--258",
journal = "Mathematical Methods of Operations Research",
issn = "1432-2994",
publisher = "SPRINGER HEIDELBERG",
number = "2",

}

Simple and three-valued simple coloring games. / Musegaas, Marieke; Borm, Peter; Quant, Marieke.

In: Mathematical Methods of Operations Research, Vol. 84, No. 2, 10.2016, p. 239-258.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Simple and three-valued simple coloring games

AU - Musegaas, Marieke

AU - Borm, Peter

AU - Quant, Marieke

PY - 2016/10

Y1 - 2016/10

N2 - In this paper minimum coloring games are considered. We characterize the class of conflict graphs inducing simple or three-valued simple minimum coloring games. We provide an upper bound on the number of maximum cliques of conflict graphs inducing such games. Moreover, a characterization of the core is provided in terms of the underlying conflict graph. In particular, in case of a perfect conflict graph the core of an induced three-valued simple minimum coloring game equals the vital core.

AB - In this paper minimum coloring games are considered. We characterize the class of conflict graphs inducing simple or three-valued simple minimum coloring games. We provide an upper bound on the number of maximum cliques of conflict graphs inducing such games. Moreover, a characterization of the core is provided in terms of the underlying conflict graph. In particular, in case of a perfect conflict graph the core of an induced three-valued simple minimum coloring game equals the vital core.

KW - minimum coloring games

KW - simple games

KW - three-valued simple games

U2 - 10.1007/s00186-016-0542-4

DO - 10.1007/s00186-016-0542-4

M3 - Article

VL - 84

SP - 239

EP - 258

JO - Mathematical Methods of Operations Research

JF - Mathematical Methods of Operations Research

SN - 1432-2994

IS - 2

ER -