N. Bansal, U. Feige, R. Krauthgamer, K. Makarychev, R. Naor et al., Min-max graph partitioning and small set expansion, Proc. of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp.17-26, 2011.

R. Brown, J. Morris, C. D. Shrimpton, and . Wensley, Graphs of morphisms of graphs, Electronic Journal of Combinatorics, vol.15, issue.1, 2008.

C. Chekuri, S. Guha, and J. Naor, The steiner k-cut problem, SIAM Journal on Discrete Mathematics, vol.20, issue.1, pp.261-271, 2006.

R. Chitnis, M. Hajiaghayi, and D. Marx, Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset, Proc. of the, p.23

, Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.1713-1725, 2012.

M. Rajesh-hemant-chitnis, M. Cygan, M. Hajiaghayi, M. Pilipczuk, and . Pilipczuk, Designing FPT algorithms for cut problems using randomized contractions, Proc. of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.460-469, 2012.

L. Rajesh-hemant-chitnis, D. Egri, and . Marx, List H-coloring a graph by removing few vertices, Proc. of the 21st Annual European Symposium on Algorithms (ESA), vol.8125, pp.313-324, 2013.

M. Cygan, D. Lokshtanov, M. Pilipczuk, M. , and S. Saurabh, Minimum bisection is fixed parameter tractable, Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pp.323-332, 2014.

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The complexity of multiterminal cuts, SIAM Journal on Computing, issue.4, pp.864-894, 1994.

J. Díaz, M. Serna, and D. M. Thilikos, Efficient algorithms for counting parameterized list H-colorings, Journal of Computer and System Sciences, vol.74, issue.5, pp.919-937, 2008.

J. Díaz, M. J. Serna, D. M. Thilikos, C. , and K. ). , coloring: Fast, easy, and hard cases, Proc. of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS), vol.2136, pp.304-315, 2001.

J. Díaz, M. J. Serna, and D. M. Thilikos, Fixed parameter algorithms for counting and deciding bounded restrictive list h-colorings, Proc. of the 12th Annual European Symposium on Algorithms (ESA), vol.3221, pp.275-286, 2004.

L. Egri, P. Hell, B. Larose, and A. Rafiey, Space complexity of list Hcolouring: a dichotomy, Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.349-365, 2014.

L. Egri, A. Krokhin, B. Larose, and P. Tesson, The complexity of the list homomorphism problem for graphs. Theory of Computing Systems, vol.51, pp.143-178, 2012.
URL : https://hal.archives-ouvertes.fr/inria-00455321

G. Even, J. Naor, B. Schieber, and M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, vol.20, issue.2, pp.151-174, 1998.

T. Feder, P. Hell, and J. Huang, List homomorphisms and circular arc graphs, Combinatorica, vol.19, issue.4, pp.487-505, 1999.

T. Feder, P. Hell, and J. Huang, Bi-arc graphs and the complexity of list homomorphisms, Journal of Graph Theory, vol.42, issue.1, pp.61-80, 2003.

N. Garg, V. V. Vazirani, and M. Yannakakis, Multiway cuts in node weighted graphs, Journal of Algorithms, vol.50, issue.1, pp.49-61, 2004.

X. Michel, D. P. Goemans, and . Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, vol.42, issue.6, pp.1115-1145, 1995.

M. Grohe, K. Kawarabayashi, D. Marx, and P. Wollan, Finding topological subgraphs is fixed-parameter tractable, Proc. of the 43rd ACM Symposium on Theory of Computing (STOC), pp.479-488, 2011.

F. Hadlock, Finding a maximum cut of a planar graph in polynomial time, SIAM Journal on Computing, vol.4, issue.3, pp.221-225, 1975.

P. Hell and J. Ne?et?il, Graphs and homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol.28, 2004.

P. Hell and A. Rafiey, The dichotomy of list homomorphisms for digraphs, Proc. of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.1703-1713, 2011.

K. Ichi-kawarabayashi and M. Thorup, The minimum k-way cut of bounded size is fixed-parameter tractable, Proc. of the 54th Annual Symposium on Foundations of Computer Science (FOCS), pp.160-169, 2013.

D. R. Karger, P. Klein, C. Stein, M. Thorup, and N. E. Young, Rounding algorithms for a geometric embedding of minimum multiway cut, Proc. of the, p.31

, Annual ACM Symposium on Theory of Computing (STOC), pp.668-678, 1999.

M. Lefteris, M. Kirousis, P. Serna, and . Spirakis, Parallel complexity of the connected subgraph problem, SIAM Journal on Computing, vol.22, issue.3, pp.573-586, 1993.

D. Marx, Parameterized graph separation problems, Theoretical Computer Science, vol.351, issue.3, pp.394-406, 2006.

D. Marx, O. Barry, I. Sullivan, and . Razgon, Finding small separators in linear time via treewidth reduction, ACM Transactions on Algorithms, vol.9, issue.4, p.30, 2013.

D. Marx and I. Razgon, Fixed-parameter tractability of multicut parameterized by the size of the cutset, SIAM Journal on Computing, vol.43, issue.2, pp.355-388, 2014.

H. Räcke, Optimal hierarchical decompositions for congestion minimization in networks, Proc. of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp.255-264, 2008.

R. Ravi and A. Sinha, Approximating k-cuts via network strength, Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.621-622, 2002.

M. Stoer and F. Wagner, A simple min-cut algorithm, Journal of the ACM, vol.44, issue.4, pp.585-591, 1997.

Z. Svitkina and É. Tardos, Min-max multiway cut, Proc. of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and 8th International Workshop on Randomization and Computation (RANDOM), vol.3122, pp.207-218, 2004.