{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:48:35Z","timestamp":1725558515073},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540406716"},{"type":"electronic","value":"9783540451389"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45138-9_29","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T18:41:48Z","timestamp":1277232108000},"page":"348-357","source":"Crossref","is-referenced-by-count":1,"title":["A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs"],"prefix":"10.1007","author":[{"given":"Zhi-Zhong","family":"Chen","sequence":"first","affiliation":[]},{"given":"Mitsuharu","family":"Kouno","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"K. Appel","year":"1977","unstructured":"Appel, K., Haken, W.: Every planar map is four colorable, Part I: Discharging. Illinois J. Math.\u00a021, 429\u2013490 (1977)","journal-title":"Illinois J. Math."},{"key":"29_CR2","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1215\/ijm\/1256049012","volume":"21","author":"K. Appel","year":"1977","unstructured":"Appel, K., Haken, W., Koch, J.: Every planar map is four colorable, Part II: Reducibility. Illinois J. Math.\u00a021, 491\u2013567 (1977)","journal-title":"Illinois J. Math."},{"key":"29_CR3","first-page":"89","volume":"39","author":"D. Archdeacon","year":"1983","unstructured":"Archdeacon, D.: Coupled colorings of planar graphs. Congres. Numer.\u00a039, 89\u201394 (1983)","journal-title":"Congres. Numer."},{"key":"29_CR4","first-page":"12","volume":"41","author":"O.V. Borodin","year":"1984","unstructured":"Borodin, O.V.: Solution of Ringel\u2019s problems on vertex-face coloring of planar graphs and coloring of 1-planar graphs (in Russian). Met. Discret. anal., Novosibirsk\u00a041, 12\u201326 (1984)","journal-title":"Met. Discret. anal., Novosibirsk"},{"key":"29_CR5","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1002\/jgt.3190190406","volume":"19","author":"O.V. Borodin","year":"1995","unstructured":"Borodin, O.V.: A new proof of the 6 color theorem. J. Graph Theory\u00a019, 507\u2013521 (1995)","journal-title":"J. Graph Theory"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jagm.2001.1178","volume":"41","author":"Z.-Z. Chen","year":"2001","unstructured":"Chen, Z.-Z.: Approximation algorithms for independent sets in map graphs. J. Algorithms\u00a041, 20\u201340 (2001)","journal-title":"J. Algorithms"},{"key":"29_CR7","doi-asserted-by":"crossref","unstructured":"Chen, Z.-Z., Grigni, M., Papadimitriou, C.H.: Planar map graphs. In: Proc. ACM STOC 1998, pp. 514\u2013523 (1998)","DOI":"10.1145\/276698.276865"},{"key":"29_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1145\/506147.506148","volume":"49","author":"Z.-Z. Chen","year":"2002","unstructured":"Chen, Z.-Z., Grigni, M., Papadimitriou, C.H.: Map graphs. J. ACM\u00a049, 127\u2013138 (2002)","journal-title":"J. ACM"},{"key":"29_CR9","first-page":"470","volume":"8","author":"N. Chiba","year":"1981","unstructured":"Chiba, N., Nishizeki, T., Saito, N.: A linear 5-coloring algorithm of planar graphs. J. Algorithms.\u00a08, 470\u2013479 (1981)","journal-title":"J. Algorithms."},{"key":"29_CR10","unstructured":"Chrobak, M., Diks, K.: Two algorithms for coloring planar graphs with 5 colors. Tech. Report, Columbia University (January 1987)"},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(84)90056-5","volume":"19","author":"G.N. Frederickson","year":"1984","unstructured":"Frederickson, G.N.: On linear-time algorithms for five-coloring planar graphs. Inform. Process. Lett.\u00a019, 219\u2013224 (1984)","journal-title":"Inform. Process. Lett."},{"key":"29_CR12","unstructured":"Matula, D.W., Shiloach, Y., Tarjan, R.E.: Two linear-time algorithms for fivecoloring a planar graph. Tech. Report STAN-CS-80-830, Stanford University (November 1980)"},{"key":"29_CR13","first-page":"287","volume-title":"Recent Progress in Combinatorics (Proc. 3rd Waterloo Conf. on Combinatorics, 1968)","author":"O. Ore","year":"1969","unstructured":"Ore, O., Plummer, M.D.: Cyclic coloration of planar graphs. In: Recent Progress in Combinatorics (Proc. 3rd Waterloo Conf. on Combinatorics, 1968), pp. 287\u2013293. Academic Press, New York (1969)"},{"key":"29_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02996313","volume":"29","author":"G. Ringel","year":"1965","unstructured":"Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamburg\u00a029, 107\u2013117 (1965)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"29_CR15","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1093\/comjnl\/28.1.78","volume":"28","author":"M.H. Williams","year":"1985","unstructured":"Williams, M.H.: A linear algorithm for colouring planar graphs with five colours. Comput. J.\u00a028, 78\u201381 (1985)","journal-title":"Comput. J."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45138-9_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T05:53:58Z","timestamp":1559195638000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45138-9_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540406716","9783540451389"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45138-9_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}