{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:05Z","timestamp":1759638125530},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_27","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"313-324","source":"Crossref","is-referenced-by-count":3,"title":["List H-Coloring a Graph by Removing Few Vertices"],"prefix":"10.1007","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[]},{"given":"L\u00e1szl\u00f3","family":"Egri","sequence":"additional","affiliation":[]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/978-3-642-31594-7_20","volume-title":"Automata, Languages, and Programming","author":"R. Chitnis","year":"2012","unstructured":"Chitnis, R., Cygan, M., Hajiaghayi, M., Marx, D.: Directed subset feedback vertex set is fixed-parameter tractable. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 230\u2013241. Springer, Heidelberg (2012)"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. In: SODA (2012)","DOI":"10.1137\/1.9781611973099.136"},{"key":"27_CR3","series-title":"Formal Models and Semantics","first-page":"193","volume-title":"Handbook of Theoretical Computer Science","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science. Formal Models and Semantics, vol.\u00a0B, pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-28050-4_1","volume-title":"Parameterized and Exact Computation","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 1\u201312. Springer, Heidelberg (2012)"},{"key":"27_CR5","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer"},{"key":"27_CR6","unstructured":"Egri, L., Hell, P., Larose, B., Rafiey, A.: An L vs. NL dichotomy for the digraph list homomorphism problem (2013) (manuscript in preparation)"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Egri, L., Krokhin, A.A., Larose, B., Tesson, P.: The complexity of the list homomorphism problem for graphs. Theory of Computing Systems\u00a051(2) (2012)","DOI":"10.1007\/s00224-011-9333-8"},{"issue":"2","key":"27_CR8","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jctb.1997.1812","volume":"72","author":"T. Feder","year":"1998","unstructured":"Feder, T., Hell, P.: List homomorphisms to reflexive graphs. J. Comb. Theory, Ser. B\u00a072(2), 236\u2013250 (1998)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"27_CR9","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s004939970003","volume":"19","author":"T. Feder","year":"1999","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica\u00a019(4), 487\u2013505 (1999)","journal-title":"Combinatorica"},{"issue":"1","key":"27_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/jgt.10073","volume":"42","author":"T. Feder","year":"2003","unstructured":"Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms. Journal of Graph Theory\u00a042(1), 61\u201380 (2003)","journal-title":"Journal of Graph Theory"},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.disc.2005.09.030","volume":"307","author":"T. Feder","year":"2007","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms of graphs with bounded degrees. Discrete Mathematics\u00a0307, 386\u2013392 (2007)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"27_CR12","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput.\u00a028(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"27_CR13","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1016\/j.dam.2005.11.006","volume":"154","author":"G. Gutin","year":"2006","unstructured":"Gutin, G., Rafiey, A., Yeo, A.: Minimum cost and list homomorphisms to semicomplete digraphs. Discrete Applied Mathematics\u00a0154, 890\u2013897 (2006)","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR15","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and homomorphisms. Oxford University Press"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Hell, P., Rafiey, A.: The dichotomy of list homomorphisms for digraphs. In: SODA, pp. 1703\u20131713 (2011)","DOI":"10.1137\/1.9781611973082.131"},{"key":"27_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/978-3-642-31594-7_49","volume-title":"Automata, Languages, and Programming","author":"S. Kratsch","year":"2012","unstructured":"Kratsch, S., Pilipczuk, M., Pilipczuk, M., Wahlstr\u00f6m, M.: Fixed-parameter tractability of multicut in directed acyclic graphs. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 581\u2013593. Springer, Heidelberg (2012)"},{"key":"27_CR19","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.ic.2012.10.016","volume":"222","author":"D. Lokshtanov","year":"2013","unstructured":"Lokshtanov, D., Marx, D.: Clustering with local restrictions. Inf. Comput.\u00a0222, 278\u2013292 (2013)","journal-title":"Inf. Comput."},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1007\/978-3-642-31594-7_63","volume-title":"Automata, Languages, and Programming","author":"D. Lokshtanov","year":"2012","unstructured":"Lokshtanov, D., Ramanujan, M.S.: Parameterized tractability of multiway cut with parity constraints. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 750\u2013761. Springer, Heidelberg (2012)"},{"issue":"3","key":"27_CR21","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR22","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. CoRR, abs\/1110.4765 (2011)"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: STOC, pp. 469\u2013478 (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"issue":"4","key":"27_CR25","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B.A. Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett.\u00a032(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T13:11:32Z","timestamp":1558012292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}