J. Araújo, J. Baste, and I. Sau, Ruling out FPT algorithms for Weighted Coloring on forests, Theoretical Computer Science, vol.729, pp.11-19, 2018.

J. Araújo, N. Nisse, and S. Pérennes, Weighted coloring in trees, SIAM Journal on Discrete Mathematics, vol.28, issue.4, pp.2029-2041, 2014.

M. Basavaraju, M. C. Francis, M. S. Ramanujan, and S. Saurabh, Partially polynomial kernels for set cover and test cover, SIAM Journal on Discrete Mathematics, vol.30, issue.3, pp.1401-1423, 2016.

H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, On problems without polynomial kernels, Journal of Computer and System Sciences, vol.75, issue.8, pp.423-434, 2009.

H. L. Bodlaender, B. M. Jansen, and S. Kratsch, Kernelization lower bounds by crosscomposition, SIAM Journal on Discrete Mathematics, vol.28, issue.1, pp.277-305, 2014.

H. L. Bodlaender, S. Thomassé, and A. Yeo, Kernel bounds for disjoint cycles and disjoint paths, Theoretical Computer Science, vol.412, issue.35, pp.4570-4578, 2011.
URL : https://hal.archives-ouvertes.fr/lirmm-00806805

É. Bonnet and V. T. Paschos, Dual parameterization and parameterized approximability of subset graph problems. RAIRO -Operations Research, vol.51, pp.261-266, 2017.

B. Chor, M. Fellows, and D. W. Juedes, Linear Kernels in Linear Time, or How to Save k Colors in O(n 2 ) Steps, Proc. of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol.3353, pp.257-269, 2004.

M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx et al., Parameterized Algorithms, 2015.

D. De-werra, M. Demange, B. Escoffier, J. Monnot, and V. T. Paschos, Weighted coloring on planar, bipartite and split graphs: Complexity and approximation, Discrete Applied Mathematics, vol.157, issue.4, pp.819-832, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00004074

M. Demange, D. De-werra, J. Monnot, and V. T. Paschos, Weighted node coloring: When stable sets are expensive, Proc. of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 2573 of LNCS, pp.114-125, 2002.

M. Demange, P. Grisoni, and V. T. Paschos, Approximation results for the minimum graph coloring problem, Information Processing Letters, vol.50, issue.1, pp.19-23, 1994.

R. Diestel, Graph Theory, vol.173, 2010.

M. Dom, D. Lokshtanov, and S. Saurabh, Kernelization Lower Bounds Through Colors and IDs, ACM Transactions on Algorithms, vol.11, issue.2, 2014.

R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science, 2013.

R. Duh and M. Fürer, Approximation of k-Set Cover by Semi-Local Optimization, Proc. of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pp.256-264, 1997.

B. Escoffier, J. Monnot, and V. T. Paschos, Weighted coloring: further complexity and approximability results, Information Processing Letters, vol.97, issue.3, pp.98-103, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00116712

F. V. Fomin and D. Kratsch, Exact Exponential Algorithms, Texts in Theoretical Computer Science. An EATCS Series, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00085561

L. Fortnow and R. Santhanam, Infeasibility of instance compression and succinct PCPs for NP, Journal of Computer and System Sciences, vol.77, issue.1, pp.91-106, 2011.

D. Fulkerson and O. Gross, Incidence matrices and interval graphs, Pacific journal of mathematics, vol.15, issue.3, pp.835-855, 1965.

D. J. Guan and X. Zhu, A coloring problem for weighted graphs, Information Processing Letters, vol.61, issue.2, pp.77-81, 1997.

G. Z. Gutin, M. Jones, and A. Yeo, Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems, Theoretical Computer Science, vol.412, issue.41, pp.5744-5751, 2011.

M. M. Halldórsson, Approximating discrete collections via local improvements, Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.160-169, 1995.

M. M. Halldórsson, Approximating k-Set Cover and Complementary Graph Coloring, Proc. of the 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO), vol.1084, pp.118-131, 1996.

R. Hassin and S. Lahav, Maximizing the number of unused colors in the vertex coloring problem, Information Processing Letters, vol.52, issue.2, pp.87-90, 1994.

F. Havet and L. Sampaio, On the Grundy and b-Chromatic Numbers of a Graph, Algorithmica, vol.65, issue.4, pp.885-899, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00905927

D. Hermelin and X. Wu, Weak compositions and their applications to polynomial lower bounds for kernelization, Proc. of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.104-113, 2012.

R. Impagliazzo and R. Paturi, On the Complexity of k-SAT, Journal of Computer and System Sciences, vol.62, issue.2, pp.367-375, 2001.

R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity?, Journal of Computer and System Sciences, vol.63, issue.4, pp.512-530, 2001.

R. M. Karp, Reducibility among combinatorial problems, Proc. 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.24, issue.1, pp.1-14, 2012.

E. L. Lawler, A note on the complexity of the chromatic number problem, Information Processing Letters, vol.5, issue.3, pp.66-67, 1976.

D. Lokshtanov, D. Marx, and S. Saurabh, Lower bounds based on the Exponential Time Hypothesis, Bulletin of the EATCS, vol.105, pp.41-72, 2011.

S. V. Pemmaraju, S. Penumatcha, and R. Raman, Approximating interval coloring and max-coloring in chordal graphs, ACM Journal of Experimental Algorithmics, vol.10, 2005.

C. Yap, Some consequences of non-uniform conditions on uniform classes, Theoretical Computer Science, vol.26, pp.287-300, 1983.