Ruling out FPT algorithms for Weighted Coloring on forests, Theoretical Computer Science, vol.729, pp.11-19, 2018. ,
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
Partially Polynomial Kernels for Set Cover and Test Cover, SIAM Journal on Discrete Mathematics, vol.30, issue.3, pp.1401-1423, 2016. ,
Set Partitioning via Inclusion-Exclusion, SIAM Journal on Computing, vol.39, issue.2, pp.546-563, 2009. ,
On problems without polynomial kernels, Journal of Computer and System Sciences, vol.75, issue.8, pp.423-434, 2009. ,
Kernelization Lower Bounds by Cross-Composition, SIAM Journal on Discrete Mathematics, vol.28, issue.1, pp.277-305, 2014. ,
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
Dual parameterization and parameterized approximability of subset graph problems, RAIRO - Operations Research, vol.51, issue.1, pp.261-266, 2017. ,
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. ,
Advanced kernelization algorithms, Parameterized Algorithms, pp.285-319, 2015. ,
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
Weighted Node Coloring: When Stable Sets Are Expensive, Graph-Theoretic Concepts in Computer Science, pp.114-125, 2002. ,
Approximation results for the minimum graph coloring problem, Information Processing Letters, vol.50, issue.1, pp.19-23, 1994. ,
Extremal Graph Theory, Graph Theory, vol.173, pp.173-207, 2017. ,
Kernelization Lower Bounds Through Colors and IDs, ACM Transactions on Algorithms, vol.11, issue.2, pp.1-20, 2014. ,
Parameterized Approximation, Texts in Computer Science, pp.623-644, 2013. ,
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. ,
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
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
Time Versus Space, Exact Exponential Algorithms, pp.161-170, 2010. ,
Infeasibility of instance compression and succinct PCPs for NP, Journal of Computer and System Sciences, vol.77, issue.1, pp.91-106, 2011. ,
Incidence matrices and interval graphs, Pacific Journal of Mathematics, vol.15, issue.3, pp.835-855, 1965. ,
A Characterization of Comparability Graphs and of Interval Graphs, Canadian Journal of Mathematics, vol.16, pp.539-548, 1964. ,
A coloring problem for weighted graphs, Information Processing Letters, vol.61, issue.2, pp.77-81, 1997. ,
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. ,
Approximating discrete collections via local improvements, Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.160-169, 1995. ,
Approximating k-set cover and complementary graph coloring, Integer Programming and Combinatorial Optimization, vol.1084, pp.118-131, 1996. ,
Maximizing the number of unused colors in the vertex coloring problem, Information Processing Letters, vol.52, issue.2, pp.87-90, 1994. ,
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
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. ,
On the Complexity of k-SAT, Journal of Computer and System Sciences, vol.62, issue.2, pp.367-375, 2001. ,
Which Problems Have Strongly Exponential Complexity?, Journal of Computer and System Sciences, vol.63, issue.4, pp.512-530, 2001. ,
Reducibility among Combinatorial Problems, Complexity of Computer Computations, pp.85-103, 1972. ,
Max-coloring paths: tight bounds and extensions, Journal of Combinatorial Optimization, vol.24, issue.1, pp.1-14, 2010. ,
A note on the complexity of the chromatic number problem, Information Processing Letters, vol.5, issue.3, pp.66-67, 1976. ,
Normal Helly circular-arc graphs and its subclasses, Discrete Applied Mathematics, vol.161, issue.7-8, pp.1037-1059, 2013. ,
Characterizations and recognition of circular-arc graphs and subclasses: A survey, Discrete Mathematics, vol.309, issue.18, pp.5618-5635, 2009. ,
Lower bounds based on the Exponential Time Hypothesis, Bulletin of the EATCS, vol.105, pp.41-72, 2011. ,
Approximating interval coloring and max-coloring in chordal graphs, ACM Journal of Experimental Algorithmics, vol.10, 2005. ,
Matrix characterizations of circular-arc graphs, Pacific Journal of Mathematics, vol.39, issue.2, pp.535-545, 1971. ,
Some consequences of non-uniform conditions on uniform classes, Theoretical Computer Science, vol.26, issue.3, pp.287-300, 1983. ,