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. ,
Partially polynomial kernels for set cover and test cover, SIAM Journal on Discrete Mathematics, vol.30, issue.3, pp.1401-1423, 2016. ,
On problems without polynomial kernels, Journal of Computer and System Sciences, vol.75, issue.8, pp.423-434, 2009. ,
Kernelization lower bounds by crosscomposition, 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, pp.261-266, 2017. ,
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. ,
, Parameterized Algorithms, 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, Proc. of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 2573 of LNCS, pp.114-125, 2002. ,
Approximation results for the minimum graph coloring problem, Information Processing Letters, vol.50, issue.1, pp.19-23, 1994. ,
Graph Theory, vol.173, 2010. ,
Kernelization Lower Bounds Through Colors and IDs, ACM Transactions on Algorithms, vol.11, issue.2, 2014. ,
Fundamentals of Parameterized Complexity. Texts in Computer Science, 2013. ,
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. ,
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
Exact Exponential Algorithms, Texts in Theoretical Computer Science. An EATCS Series, 2010. ,
URL : https://hal.archives-ouvertes.fr/hal-00085561
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 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, Proc. of the 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 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, 2013. ,
URL : https://hal.archives-ouvertes.fr/hal-00905927
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. ,
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, Proc. of a symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp.85-103, 1972. ,
Max-coloring paths: tight bounds and extensions, Journal of Combinatorial Optimization, vol.24, issue.1, pp.1-14, 2012. ,
A note on the complexity of the chromatic number problem, Information Processing Letters, vol.5, issue.3, pp.66-67, 1976. ,
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. ,
Some consequences of non-uniform conditions on uniform classes, Theoretical Computer Science, vol.26, pp.287-300, 1983. ,