{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T10:08:56Z","timestamp":1771236536938,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540590422","type":"print"},{"value":"9783540491750","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_92","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:59:13Z","timestamp":1330275553000},"page":"409-420","source":"Crossref","is-referenced-by-count":11,"title":["The \u03c7t-coloring problem"],"prefix":"10.1007","author":[{"given":"Damon","family":"Kaller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arvind","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom","family":"Shermer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree decomposable graphs. J. Algorithms, 12:308\u2013340, 1991.","journal-title":"J. Algorithms"},{"key":"36_CR2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02582936","volume":"1","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s and A.J. Harris. List-colourings of graphs. Graphs and Combinatorics, 1:115\u2013127, 1985.","journal-title":"Graphs and Combinatorics"},{"key":"36_CR3","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"M.W. Bern","year":"1987","unstructured":"M.W. Bern, E.L. Lawler, and A.L. Wong. Linear-time computation of optimal subgraphs of decomposable graphs. J. Algorithms, 8:216\u2013235, 1987.","journal-title":"J. Algorithms"},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Proc. 25 th STOC, pages 226\u2013234, 1993.","DOI":"10.1145\/167088.167161"},{"key":"36_CR5","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"R.B. Borie, R.G. Parker, and C.A. Tovey. Automatic generation of lineartime algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica, 7:555\u2013581, 1992.","journal-title":"Algorithmica"},{"key":"36_CR6","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85:12\u201375, 1990.","journal-title":"Information and Computation"},{"key":"36_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979."},{"key":"36_CR8","volume-title":"Tree Automata","author":"F. G\u00e9cseg","year":"1984","unstructured":"F. G\u00e9cseg and M. Steinby. Tree Automata. Akad\u00e9miai Kiad\u00f3, Budapest, 1984."},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"T.R. Jensen and B. Toft. Graph Coloring Problems. Wiley Interscience, 1995.","DOI":"10.1002\/9781118032497"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"D.G. Kirkpatrick and P. Hell. On the complexity of a generalized matching problem. In Proc. 10 th STOC, pages 240\u2013245, 1978.","DOI":"10.1145\/800133.804353"},{"key":"36_CR11","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0012-365X(88)90210-5","volume":"72","author":"F. Kitagawa","year":"1988","unstructured":"F. Kitagawa and H. Ikeda. An existential problem of a weight-controlled subset and its application to school timetable construction. Discrete Mathematics, 72:195\u2013211, 1988.","journal-title":"Discrete Mathematics"},{"key":"36_CR12","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0305-0548(86)90061-4","volume":"13","author":"V. Lotfi","year":"1986","unstructured":"V. Lotfi and S. Sarin. A graph coloring algorithm for large scale scheduling problems. Comput. & Ops. Res., 13:27\u201332, 1986.","journal-title":"Comput. & Ops. Res."},{"key":"36_CR13","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1080\/00029890.1973.11993408","volume":"80","author":"W. Meyer","year":"1973","unstructured":"W. Meyer. Equitable coloring. Amer. Math. Monthly, 80:920\u2013922, 1973.","journal-title":"Amer. Math. Monthly"},{"key":"36_CR14","unstructured":"S. Mahajan and J.G. Peters. Algorithms for regular properties in recursive graphs. In Proc. 25th Ann. Allerton Conf. Communication, Control, Comput., pages 14\u201323, 1987."},{"key":"36_CR15","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7:309\u2013322, 1986.","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_92.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:17Z","timestamp":1605648317000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_92"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_92","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}