{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:39Z","timestamp":1725663699542},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540552109"},{"type":"electronic","value":"9783540467755"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55210-3_199","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T04:54:07Z","timestamp":1330232047000},"page":"389-400","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["The complexity of colouring circle graphs"],"prefix":"10.1007","author":[{"given":"Walter","family":"Unger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"31_CR1","unstructured":"A. Bouchet, Reducing prime graphs and recognizing circle graphs, Combinatorica, 1975"},{"key":"31_CR2","unstructured":"A. Bouchet, Characterizing and recognizing circle graphs, Proc. of the 6th Yugoslav Seminar on Graph Theory, Dubrovnik 1985"},{"key":"31_CR3","unstructured":"Andreas Brandst\u00e4dt, Special graph classes \u2014 a survey (preliminary version), Forschungsergebnisse Friedrich-Schiller-Universit\u00e4t Jena, Sektion Mathematik, 1990"},{"key":"31_CR4","unstructured":"Peter Damaschke, The Hamilton Cycle Probelm isNP-Complete for Circle Graphs, Technical Report, University of Jena, O-6900 Jena, Germany"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"S. Even and A. Itai, Queues, stacks and graphs, Theory of Machines and Computations, 1971, 71\u201386","DOI":"10.1016\/B978-0-12-417750-5.50011-7"},{"key":"31_CR6","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0195-6698(84)80005-0","volume":"5","author":"H. Fraysseix de","year":"1984","unstructured":"H. de Fraysseix, A Characterization of Circle Graphs, Europ. J. Combinatorics, Vol 5, 1984, 223\u2013238","journal-title":"Europ. J. Combinatorics"},{"key":"31_CR7","unstructured":"C.P. Gabor and W.-L. Hsu and K.J. Supowit, Recognizing Circle Graphs in Polynomial Time, FOCS, 85"},{"issue":"No.2","key":"31_CR8","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"M.R. Garey and D.S. Johnson and G.L. Miller and Ch.H. Papadimitriou, The Complexity of Coloring Circular Arcs and Chords, SIAM Alg. Disc. Meth., 1. No. 2., 1980, 216\u2013227","journal-title":"SIAM Alg. Disc. Meth."},{"key":"31_CR9","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1002\/net.3230030305","volume":"3","author":"F. Gavril","year":"1975","unstructured":"F. Gavril, Algorithms for a Maximum Clique and A Maximum Independent Set of a Circle Graph, Networks 3, 1975, 261\u2013273","journal-title":"Networks"},{"key":"31_CR10","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U.I. Gupta","year":"1982","unstructured":"U.I. Gupta and D.T. Lee and J.Y.T. Leung, Efficient Algorithms for Interval Graphs and Circular-Arc Graphs, Networks, 12, 1982, 459\u2013467","journal-title":"Networks"},{"key":"31_CR11","unstructured":"J.M. Keil, The Dominating Set Problem for Circle Graphs isNP-Complete, Personal communications with A. Brandst\u00e4dt"},{"issue":"11","key":"31_CR12","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/0196-6774(84)90037-3","volume":"5","author":"J.Y.-T. Leung","year":"1984","unstructured":"J.Y.-T. Leung, Fast Algorithms for Generating All Maximal Independent Sets of Interval, Circular-Arc and Chordal Graphs, Journal of Algorithms 5, 1984, 11, 22\u201335","journal-title":"Journal of Algorithms"},{"key":"31_CR13","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0012-365X(85)90117-7","volume":"54","author":"W. Naji","year":"1985","unstructured":"W. Naji, Reconnaissance des graphes de cordes, Discr. Math. 54, 1985, 329\u2013337","journal-title":"Discr. Math."},{"issue":"No.2","key":"31_CR14","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1137\/0602012","volume":"2","author":"J.B. Orlin","year":"1982","unstructured":"J.B. Orlin and M.A. Bonuccelli and D.P. Bovet, An O(n2) Algorithm for Coloring Proper Circular Arc Graphs, SIAM Alg. Disc. Meth., 2. No. 2., June 1982, 88\u201393","journal-title":"SIAM Alg. Disc. Meth."},{"key":"31_CR15","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1002\/jgt.3190060309","volume":"6","author":"R.C. Read","year":"1982","unstructured":"R.C. Read and D. Rotem and J. Urrutia, Orientation of Circle Graphs, Journal of Graph Theory, 6, 1982, 325\u2013341","journal-title":"Journal of Graph Theory"},{"key":"31_CR16","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1002\/net.3230110305","volume":"11","author":"D. Rotyem","year":"1981","unstructured":"D. Rotyem and J. Urrutia, Finding Maximum Cliques in Circle Graphs, Networks, 11, 1981, 269\u2013278","journal-title":"Networks"},{"key":"31_CR17","volume-title":"Manuscript","author":"J.P. Spinrad","year":"1988","unstructured":"J.P. Spinrad, Recognition of Circle Graphs, Manuscript 1988, Dept. of CS, Vanderbilt Univ., Nashville, TN"},{"key":"31_CR18","unstructured":"L. Stewart and E. Elmallah and J. Culberson, Polynomial algorithms on kpolygon graphs, Proc. 21th SE Conf. Combin. Graph Theory and Computing, Boca Raton, Florida 1990"},{"issue":"No.1","key":"31_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A. Tucker","year":"1980","unstructured":"A. Tucker, An Efficient Test for Circular-Arc Graphs, SIAM J. Comput. Vol. 9. No. 1., 1980, 1\u201324","journal-title":"SIAM J. Comput."},{"key":"31_CR20","unstructured":"W. Unger, F\u00e4rbung von Kreissehnengraphen, Ph.D. Thesis, University of Paderborn, Germany"},{"key":"31_CR21","doi-asserted-by":"crossref","unstructured":"W. Unger, On the k-colouring of Circle Graphs, Lecture Notes in Computer Science, 294, Springer Verlag, proc. STACS 88 Bordeaux, pp 61\u201372","DOI":"10.1007\/BFb0035832"},{"key":"31_CR22","unstructured":"W. Wessel and R. P\u00f6schel, On Circle Graphs, Graphs, Hypergraphs and Applications, 1985, 207\u2013210"},{"key":"31_CR23","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Four Pages are necessary and sufficient for Planar Graphs, ACM, 1986, 104\u2013108","DOI":"10.1145\/12130.12141"}],"container-title":["Lecture Notes in Computer Science","STACS 92"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55210-3_199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T18:30:07Z","timestamp":1578508207000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55210-3_199"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540552109","9783540467755"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-55210-3_199","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}