{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:59:33Z","timestamp":1725893973248},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735557"},{"type":"electronic","value":"9783540735564"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73556-4_38","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T15:55:47Z","timestamp":1188316547000},"page":"366-377","source":"Crossref","is-referenced-by-count":10,"title":["On the Complexity of Some Colorful Problems Parameterized by Treewidth"],"prefix":"10.1007","author":[{"given":"Michael","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Thomassen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","series-title":"London Math. Soc. Lecture Notes Series","first-page":"1","volume-title":"Surveys in Combinatorics 1993","author":"N. Alon","year":"1993","unstructured":"Alon, N.: Restricted colorings of graphs. In: Walker, K. (ed.) Surveys in Combinatorics 1993. London Math. Soc. Lecture Notes Series, vol.\u00a0187, pp. 1\u201333. Cambridge Univ. Press, Cambridge (1993)"},{"key":"38_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"38_CR3","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2005.09.027","volume":"349","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Fomin, F.V.: Equitable colorings of bounded treewidth graphs. Theoretical Computer Science\u00a0349, 22\u201330 (2005)","journal-title":"Theoretical Computer Science"},{"key":"38_CR4","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings COCOON 2007","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L., Fellows, M., Langston, M., Ragan, M.A., Rosamond, F., Weyer, M.: Quadratic kernelization for convex recoloring of trees. In: TSDM 2000. LNCS, Springer, Heidelberg (2007)"},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively generated graph families. Algorithmica\u00a07, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"38_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-73131-3","volume-title":"Proceedings COCOON 2007","author":"B. Chor","year":"2007","unstructured":"Chor, B., Fellows, M., Ragan, M.A., Razgon, I., Rosamond, F., Snir, S.: Connected coloring completion for general graphs: algorithms and complexity. In: Proceedings COCOON 2007. LNCS, Springer, Heidelberg (to appear)"},{"key":"38_CR7","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"38_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"38_CR9","first-page":"122","volume":"26","author":"P. Erd\u00f6s","year":"1980","unstructured":"Erd\u00f6s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. Congressus Numerantium\u00a026, 122\u2013157 (1980)","journal-title":"Congressus Numerantium"},{"key":"38_CR10","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"38_CR11","unstructured":"Fellows, M., Giannopoulos, P., Knauer, C., Paul, C., Rosamond, F., Whitesides, S., Yu, N.: The lawnmower and other problems: applications of MSO logic in geometry. Manuscript (2007)"},{"key":"38_CR12","unstructured":"Fellows, M., Hermelin, D., Rosamond, F.: On the fixed-parameter intractability and tractability of multiple-interval graph properties. Manuscript (2007)"},{"key":"38_CR13","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0166-218X(96)00085-6","volume":"75","author":"K. Jansen","year":"1997","unstructured":"Jansen, K., Scheffler, P.: Generalized colorings for tree-like graphs. Discrete Applied Mathematics\u00a075, 135\u2013155 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"38_CR14","volume-title":"Graph Coloring Problems","author":"T.R. Jensen","year":"1995","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley Interscience, Chichester (1995)"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/jgt.10137","volume":"44","author":"A.V. Kostochka","year":"2003","unstructured":"Kostochka, A.V., Pelsmajer, M.J., West, D.B.: A list analogue of equitable coloring. Journal of Graph Theory\u00a044, 166\u2013177 (2003)","journal-title":"Journal of Graph Theory"},{"key":"38_CR16","doi-asserted-by":"crossref","unstructured":"Kratochvil, J., Tuza, Z., Voigt, M.: New trends in the theory of graph colorings: choosability and list coloring. In: Graham, R., et al. (eds.) Contemporary Trends in Discrete Mathematics (from DIMACS and DIMATIA to the future), AMS, Providence. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a049, pp. 183\u2013197 (1999)","DOI":"10.1090\/dimacs\/049\/13"},{"key":"38_CR17","unstructured":"Marx, D.: Graph coloring with local and global constraints. Ph.D. dissertation, Department of Computer Science and Information Theory, Budapest University of Technology and Economics (2004)"},{"key":"38_CR18","doi-asserted-by":"publisher","first-page":"920","DOI":"10.2307\/2319405","volume":"80","author":"W. Meyer","year":"1973","unstructured":"Meyer, W.: Equitable coloring. American Mathematical Monthly\u00a080, 920\u2013922 (1973)","journal-title":"American Mathematical Monthly"},{"key":"38_CR19","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"38_CR20","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jctb.1994.1062","volume":"62","author":"C. Thomassen","year":"1994","unstructured":"Thomassen, C.: Every planar graph is 5-choosable. J. Combinatorial Theory Ser. B\u00a062, 180\u2013181 (1994)","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"38_CR21","doi-asserted-by":"crossref","first-page":"161","DOI":"10.7151\/dmgt.1049","volume":"17","author":"Z. Tuza","year":"1997","unstructured":"Tuza, Z.: Graph colorings with local constraints \u2014 A survey. Discussiones Mathematicae \u2013 Graph Theory\u00a017, 161\u2013228 (1997)","journal-title":"Discussiones Mathematicae \u2013 Graph Theory"},{"key":"38_CR22","first-page":"3","volume":"29","author":"V.G. Vizing","year":"1976","unstructured":"Vizing, V.G.: Coloring the vertices of a graph in prescribed colors (in Russian). Metody Diskret. Anal. v Teorii Kodov i Schem\u00a029, 3\u201310 (1976)","journal-title":"Metody Diskret. Anal. v Teorii Kodov i Schem"},{"key":"38_CR23","series-title":"London Math. Soc. Lecture Notes Series","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1017\/CBO9780511721328.012","volume-title":"Surveys in Combinatorics 2001","author":"D.R. Woodall","year":"2001","unstructured":"Woodall, D.R.: List colourings of graphs. In: Hirschfeld, J.W.P. (ed.) Surveys in Combinatorics 2001. London Math. Soc. Lecture Notes Series, vol.\u00a0288, pp. 269\u2013301. Cambridge Univ. Press, Cambridge (2001)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73556-4_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:16:18Z","timestamp":1605762978000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73556-4_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735557","9783540735564"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73556-4_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}