{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:32:50Z","timestamp":1767918770283,"version":"3.49.0"},"reference-count":23,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T00:00:00Z","timestamp":1051747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3766,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,5]]},"DOI":"10.1016\/s0166-218x(02)00242-1","type":"journal-article","created":{"date-parts":[[2003,5,12]],"date-time":"2003-05-12T23:10:20Z","timestamp":1052781020000},"page":"415-429","source":"Crossref","is-referenced-by-count":77,"title":["Parameterized complexity of vertex colouring"],"prefix":"10.1016","volume":"127","author":[{"given":"Leizhen","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(02)00242-1_BIB1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a k-tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/S0166-218X(02)00242-1_BIB2","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","article-title":"Easy problems for tree-decomposable graphs","volume":"12","author":"Arnborg","year":"1991","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00242-1_BIB3","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","article-title":"Linear time algorithms for NP-hard problems restricted to partial k-trees","volume":"23","author":"Arnborg","year":"1989","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB4","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A linear time algorithm for finding tree-decompositions of small treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB5","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0166-218X(94)90009-4","article-title":"Scheduling with incompatible jobs","volume":"55","author":"Bodlaender","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB6","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","article-title":"Fixed-parameter tractability of graph modification problems for hereditary properties","volume":"58","author":"Cai","year":"1996","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB7","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"Recognizability and second-order definability for sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","article-title":"Fixed-parameter tractability and completeness II: on completeness for W[1]","volume":"141","author":"Downey","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB9","series-title":"Parameterized Complexity","author":"Downey","year":"1999"},{"key":"10.1016\/S0166-218X(02)00242-1_BIB10","first-page":"311","article-title":"Split graphs","volume":"19","author":"F\u00f6ldes","year":"1977","journal-title":"Congr. Numer."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB11","series-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0166-218X(02)00242-1_BIB12","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph problems","volume":"1","author":"Garey","year":"1976","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB13","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","article-title":"Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph","volume":"1","author":"Gavril","year":"1972","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB14","series-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic","year":"1980"},{"issue":"3","key":"10.1016\/S0166-218X(02)00242-1_BIB15","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF02579333","article-title":"The splittance of a graph","volume":"1","author":"Hammer","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(02)00242-1_BIB16","unstructured":"T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB17","unstructured":"T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB18","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0166-218X(96)00085-6","article-title":"Generalized coloring for tree-like graphs","volume":"75","author":"Jansen","year":"1997","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB19","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","article-title":"The NP-completeness column: an ongoing guide (16)","volume":"6","author":"Johnson","year":"1985","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00242-1_BIB20","first-page":"1999","article-title":"Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs","volume":"28","author":"Kaplan","year":"1906","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00242-1_BIB21","first-page":"145","article-title":"Worst-case analysis of Read's chromatic polynomial algorithm","volume":"46","author":"Walsh","year":"1997","journal-title":"Ars Combin"},{"key":"10.1016\/S0166-218X(02)00242-1_BIB22","series-title":"Introduction to Graph Theory","author":"West","year":"1996"},{"key":"10.1016\/S0166-218X(02)00242-1_BIB23","doi-asserted-by":"crossref","unstructured":"L. Cai, B. Schieber, A linear-time algorithm for computing the intersection of all odd cycles in a graph, Discrete Appl. Math. 73 (1997) 27\u201334.","DOI":"10.1016\/S0166-218X(96)00074-1"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02002421?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02002421?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,4]],"date-time":"2019-04-04T19:24:13Z","timestamp":1554405853000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02002421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,5]]}},"alternative-id":["S0166218X02002421"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00242-1","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}