Minimum coloring games with repeated players

S. Miquel Fernández, H. Norde, H. Hamers, S. el Obadi

Some conflict problems depicted by graphs have the special feature that several copies of a player may occupy different vertices. The related cooperative games are generalization of the classical minmum coloring games. We show that they are submodular if the underlying graph is complete multipartite and they are totally balanced if and only if the underlying situation is perfect (the game is equal to the rank game corresponding to a monotonic pair).

Keywords: minimum coloring, complete r-patite, (0-1)-marginal game, submodularity, balancedness

GT19.GAMES5
November 10, 2023  12:00 PM
CC2: Conference Room

J. C. Gonçalves Dosantos, R. Martínez, J. Sánchez Soriano

D. Samaniego, L. Davila-Pena

N. Llorca Pascual