Abstract
We give an efficient local search algorithm that computes a good vertex coloring of a graph G. In order to better illustrate this local search method, we view local moves as selfish moves in a suitably defined game. In particular, given a graph G = (V,E) of n vertices and m edges, we define the graph coloring game Γ(G) as a strategic game where the set of players is the set of vertices and the players share the same action set, which is a set of n colors. The payoff that a vertex v receives, given the actions chosen by all vertices, equals the total number of vertices that have chosen the same color as v, unless a neighbor of v has also chosen the same color, in which case the payoff of v is 0. We show:
-
The game Γ(G) has always pure Nash equilibria. Each pure equilibrium is a proper coloring of G. Furthermore, there exists a pure equilibrium that corresponds to an optimum coloring.
-
We give a polynomial time algorithm \(\mathcal{A}\) which computes a pure Nash equilibrium of Γ(G).
-
The total number, k, of colors used in any pure Nash equilibrium (and thus achieved by \(\mathcal{A}\)) is \(k\leq\min\{\Delta_2+1, \frac{n+\omega}{2}, \frac{1+\sqrt{1+8m}}{2}, n-\alpha+1\}\), where ω, α are the clique number and the independence number of G and Δ 2 is the maximum degree that a vertex can have subject to the condition that it is adjacent to at least one vertex of equal or greater degree. (Δ 2 is no more than the maximum degree Δ of G.)
-
Thus, in fact, we propose here a new, efficient coloring method that achieves a number of colors satisfying (together) the known general upper bounds on the chromatic number χ. Our method is also an alternative general way of proving, constructively, all these bounds.
-
Finally, we show how to strengthen our method (staying in polynomial time) so that it avoids “bad” pure Nash equilibria (i.e. those admitting a number of colors k far away from χ). In particular, we show that our enhanced method colors optimally dense random q-partite graphs (of fixed q) with high probability.
Partially supported by the EU within the 6th Framework Programme under contract 015964 “Algorithmic Principles for Building Efficient Overlay Computers” (AEOLUS) and the ICT Programme under contract IST-2008-215270 (FRONTS), and by the General Secretariat for Research and Technology of the Greek Ministry of Development within the Programme PENED 2003.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bodlaender, H.L.: On the complexity of some coloring games. International Journal of Foundations of Computer Science 2(2), 133–147 (1991)
Bollbás, B.: The chromatic number of random graphs. Combinatorica 8, 49–55 (1988)
Brelaz, D.: New methods to color the vertices of a graph. Comm. ACM 22, 251–256 (1979)
Brooks, R.L.: On colouring the nodes of a network. Proc. Cambridge Phil. Soc. 37, 194–197 (1941)
Diestel, R.: Graph Theory. Springer, Heidelberg (2005)
Dinski, T., Zhu, X.: A bound for the game chromatic number of graphs. Discrete Mathematics 196, 109–115 (1999)
Feige, U., Kilian, J.: Zero knowledge and the chromatic number. Journal of Computer and System Sciences 57(2), 187–199 (1998)
Halldórsson, M.: A still better performance guarantee for approximate graph coloring. Information Processing Letters 45, 19–23 (1993)
Harary, F.: Graph theory. Addison-Wesley, Reading (1969)
Harary, F., Tuza, Z.: Two graph-colouring games. Bulletin of the Australian Mathematical Society 48, 141–149 (1993)
Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58, 13–30 (1963)
Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley Interscience, Hoboken (1995)
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press (1972)
Monderer, D., Shapley, L.S.: Potential games. Games and Economic Behavior 14, 124–143 (1996)
Nash, J.F.: Non-cooperative games. Annals of Mathematics 54(2), 286–295 (1951)
Stacho, L.: New upper bounds for the chromatic number of a graph. Journal of Graph Theory 36(2), 117–120 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Panagopoulou, P.N., Spirakis, P.G. (2008). A Game Theoretic Approach for Efficient Graph Coloring . In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-92182-0_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92181-3
Online ISBN: 978-3-540-92182-0
eBook Packages: Computer ScienceComputer Science (R0)