Resumen de Minimum coloring games with PMAS

Herbert Hamers , Silvia Miquel Fernández , Henk Norde

• Minimum coloring games were introduced by Deng, Ibaraki and Nagamochi (1999). A conict graph is used as a simple model of conict where each vertex represents each agent involved in the situation. Two vertices are adjacent through an edge if the corresponding agents are in conict under the situation, and the total cost of the conict is proportional to the chromatic number of the conict graph. Deng et al. (2000) showed that the minimum coloring game on a graph G is totally balanced if and only if G is perfect. A characterization of the core of the minimum coloring game on a perfect graph is provided by Okamoto (2003). In this paper, we introduce the degree consistency property of a graph and show that it implies its perfectness. Further, we show that the minimum coloring game has a PMAS if and only if the corresponding graph is degree consistent.