A. Stephen and . Cook, The complexity of theorem-proving procedures, Proceedings of the 3rd Annual ACM Symp. on Theory of Computing (STOC), pp.151-158, 1971.

D. De-werra, M. Demange, and B. Escoffier, Weighted coloring on planar, bipartite and split graphs: Complexity and approximation, Discrete Applied Mathematics, vol.157, issue.4, pp.819-832, 2009.
DOI : 10.1016/j.dam.2008.06.013
URL : https://hal.archives-ouvertes.fr/hal-00116696

M. Demange, D. De-werra, J. Monnot, V. Th, and . Paschos, Weighted Node Coloring: When Stable Sets Are Expensive, 28th Int. Work. on Graph- Theoretic Concepts in Comp. Sc. (WG), pp.114-125, 2002.
DOI : 10.1007/3-540-36379-3_11

L. Epstein and A. Levin, On the max coloring problem, Theoretical Computer Science, vol.462, pp.23-38, 2012.
DOI : 10.1016/j.tcs.2012.07.037

B. Escoffier, J. Monnot, V. Th, and . Paschos, Weighted Coloring: further complexity and approximability results, Information Processing Letters, vol.97, issue.3, pp.98-103, 2006.
DOI : 10.1016/j.ipl.2005.09.013
URL : https://hal.archives-ouvertes.fr/hal-00116712

D. J. Guan and X. Zhu, A coloring problem for weighted graphs, Information Processing Letters, vol.61, issue.2, pp.77-81, 1997.
DOI : 10.1016/S0020-0190(97)00002-1

R. Impagliazzo and R. Paturi, Complexity of k-SAT, Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317), pp.367-375, 2001.
DOI : 10.1109/CCC.1999.766282

R. M. Karp, Reducibility among combinatorial problems, Proceedings of a symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp.85-103, 1972.

T. Kavitha and J. Mestre, Max-coloring paths: tight bounds and extensions, Journal of Combinatorial Optimization, vol.18, issue.2, pp.1-14, 2012.
DOI : 10.1007/s10878-010-9290-1

C. , L. Sales, and B. Reed, Weighted coloring on graphs with bounded tree width, Annals of 19th International Symposium on Mathematical Programming, 2006.

V. Sriram, S. Pemmaraju, R. Penumatcha, and . Raman, Approximating interval coloring and max-coloring in chordal graphs Approximating interval coloring and max-coloring in chordal graphs, Proc. 3rd Int. Workshop on Experimental and Efficient Algorithms (WEA), pp.399-416, 2004.

V. Sriram, R. Pemmaraju, and . Raman, Approximation algorithms for the max-coloring problem, Proceedings 32nd International Colloquium on Automata, Languages and Programming (ICALP), pp.1064-1075, 2005.

V. Sriram, R. Pemmaraju, K. R. Raman, and . Varadarajan, Buffer minimization using max-coloring, 15th ACM-SIAM Symp. on Discrete Alg. (SODA) Max-coloring and online coloring with bandwidths on interval graphs, pp.562-571, 2004.

R. Williams, A New Algorithm for Optimal Constraint Satisfaction and Its Implications, 31st International Colloquium on Automata, Languages and Programming (ICALP), pp.1227-1237, 2004.
DOI : 10.1007/978-3-540-27836-8_101