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. Araujo, N. Nisse, and S. Pérennes, Weighted Coloring in Trees, SIAM Journal on Discrete Mathematics, vol.28, issue.4, pp.2029-2041, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00931523

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.

A. Björklund, T. Husfeldt, and M. Koivisto, Set Partitioning via Inclusion-Exclusion, SIAM Journal on Computing, vol.39, issue.2, pp.546-563, 2009.

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 Cross-Composition, 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, issue.1, 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, Graph-Theoretic Concepts in Computer Science, vol.3353, pp.257-269, 2004.

M. Cygan, F. V. Fomin, ?. Kowalik, D. Lokshtanov, D. Marx et al., Advanced kernelization algorithms, Parameterized Algorithms, pp.285-319, 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. D. Werra, J. Monnot, and V. T. Paschos, Weighted Node Coloring: When Stable Sets Are Expensive, Graph-Theoretic Concepts in Computer Science, 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, Extremal Graph Theory, Graph Theory, vol.173, pp.173-207, 2017.

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

R. G. Downey and M. R. Fellows, Parameterized Approximation, Texts in Computer Science, pp.623-644, 2013.

R. Duh and M. Fürer, Approximation of k-set cover by semi-local optimization, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97, pp.256-264, 1997.

B. Escoffier, Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results, Graph-Theoretic Concepts in Computer Science, vol.9941, pp.50-61, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01360669

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, Time Versus Space, Exact Exponential Algorithms, pp.161-170, 2010.

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.

P. C. Gilmore and A. J. Hoffman, A Characterization of Comparability Graphs and of Interval Graphs, Canadian Journal of Mathematics, vol.16, pp.539-548, 1964.

D. J. Guan and Z. Xuding, 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, Integer Programming and Combinatorial Optimization, vol.1084, pp.118-131, 1996.

R. Hassin and S. Lahav-(haddad), 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, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00905927

D. Hermelin and X. Wu, Weak Compositions and Their Applications to Polynomial Lower Bounds for Kernelization, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 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, Complexity of Computer Computations, 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, 2010.

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

M. C. Lin, F. J. Soulignac, and J. L. Szwarcfiter, Normal Helly circular-arc graphs and its subclasses, Discrete Applied Mathematics, vol.161, issue.7-8, pp.1037-1059, 2013.

M. C. Lin and J. L. Szwarcfiter, Characterizations and recognition of circular-arc graphs and subclasses: A survey, Discrete Mathematics, vol.309, issue.18, pp.5618-5635, 2009.

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.

A. Tucker, Matrix characterizations of circular-arc graphs, Pacific Journal of Mathematics, vol.39, issue.2, pp.535-545, 1971.

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