{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T07:30:07Z","timestamp":1768721407785,"version":"3.49.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":12,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540167838","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0016284","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T05:39:17Z","timestamp":1131860357000},"page":"573-581","source":"Crossref","is-referenced-by-count":6,"title":["Complexity of generalized graph coloring"],"prefix":"10.1007","author":[{"given":"Vladislav","family":"Rutenburg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"55_CR1","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"Berge, C. Graphs and Hypergraphs, North-Holland, Amsterdam, 1973."},{"key":"55_CR2","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B. Extremal Graph Theory, Academic Press, London, 1978."},{"issue":"6","key":"55_CR3","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1145\/872726.806984","volume":"17","author":"G. J. Chaitin","year":"1982","unstructured":"Chaitin, G. J. Register Allocation and Spilling via Graph Coloring, SIGPLAN Not. (1982), vol. 17, no. 6, 98\u2013105.","journal-title":"SIGPLAN Not."},{"key":"55_CR4","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R. and D. S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979."},{"key":"55_CR5","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"Garey, M. R., D. S. Johnson, L. J. Stockmeyer. \u201cSome Simplified NP-Complete Graph Problems\u201d, Theoretical Computer Science 1 (1976), 237\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"55_CR6","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I. \u201cThe NP-Completeness of Some Edge-Paritioning Problems\u201d, SIAM J. Comput., 10 (1981), 713\u2013717.","journal-title":"SIAM J. Comput."},{"key":"55_CR7","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"Karp, R. M. \u201cReducibility among Combinatorial Problems\u201d, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum, New York, 1972, 85\u2013103."},{"key":"55_CR8","unstructured":"Mansfield, A. \u201cTopics in Computational Complexity\u201d, Ph.D. Thesis, Univ. of Oxford., 1982."},{"key":"55_CR9","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C. H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C. H. and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, 1982."},{"key":"55_CR10","first-page":"216","volume-title":"The Complexity of Satisfiability Problems","author":"T. J. Schaefer","year":"1978","unstructured":"Schaefer, T. J. \u201cThe Complexity of Satisfiability Problems\u201d, Proceedings of the 10\n                  th\n                 ACM STOC, New York, 1978, 216\u2013226."},{"key":"55_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L. J. \u201cPolynomial-time Hierarchy\u201d, Theor. Computer Science 3 (1977), 1\u201322.","journal-title":"Theor. Computer Science"},{"key":"55_CR12","first-page":"253","volume-title":"Node-and Edge-Deletion NP-complete Problems","author":"M. Yannakakis","year":"1978","unstructured":"Yannakakis, M. \u201cNode-and Edge-Deletion NP-complete Problems\u201d, Proceedings of the 10\n                  th\n                 ACM STOC, New York, 1978, 253\u2013264."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016284.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:36:02Z","timestamp":1607549762000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540167838"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/bfb0016284","relation":{},"subject":[]}}