{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:03Z","timestamp":1742596803821,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569398"},{"type":"electronic","value":"9783540478263"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"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":[[1993]]},"DOI":"10.1007\/3-540-56939-1_64","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:56:49Z","timestamp":1330257409000},"page":"88-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Problems on pairs of trees and the four colour problem of planar graphs"],"prefix":"10.1007","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[]},{"given":"Alan","family":"Gibbons","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"K. Appel","year":"1977","unstructured":"K. Appel, W. Haken, \u201cEvery planar map is four colorable, Part I: discharging\u201d, Illinois Journal of Mathematics, Vol. 21, 1977, pp. 429\u2013490.","journal-title":"Illinois Journal of Mathematics"},{"key":"8_CR2","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1215\/ijm\/1256049012","volume":"21","author":"K. Appel","year":"1977","unstructured":"K. Appel, W. Haken, J. Koch, \u201cEvery planar map is four colorable, Part II: reducibility\u201d, Illinois Journal of Mathematics, Vol. 21, 1977, pp. 491\u2013567.","journal-title":"Illinois Journal of Mathematics"},{"key":"8_CR3","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0196-6774(89)90012-6","volume":"10","author":"N. Chiba","year":"1989","unstructured":"N. Chiba, T. Nishizeki, \u201cThe hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs\u201d, Journal of Algorithms, Vol. 10, 1989, pp. 187\u2013211.","journal-title":"Journal of Algorithms"},{"key":"8_CR4","unstructured":"A. M. Gibbons, \u201cAlgorithmic Graph Theory\u201d, Cambridge University Press, 1985."},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"J.E. Hopcroft, R.E. Tarjan, \u201cDividing a graph into triconnected components\u201d, SIAM Journal of Computing, 1973, pp. 135\u2013158.","DOI":"10.1137\/0202012"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"T-s. Hsu, \u201cOn four-connecting a triconnected graph\u201d, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992, pp. 70\u201379.","DOI":"10.1109\/SFCS.1992.267817"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"A. Kanevsky, R. Tamassia, G. Di Battista, J. Chen, \u201cOn-line maintenance of the four-connected components of a graph\u201d, Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 793\u2013801.","DOI":"10.1109\/SFCS.1991.185451"},{"key":"8_CR8","volume-title":"The Four Color Problem","author":"O. Ore","year":"1967","unstructured":"O. Ore, \u201cThe Four Color Problem\u201d, New York, Academic Press, 1967."},{"key":"8_CR9","unstructured":"T.L. Saaty, P.C. Kainen, \u201cThe Four-Color Problem. Assaults and Conquest\u201d, McGraw-Hill, 1977."},{"key":"8_CR10","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1090\/S0002-9947-1956-0081471-8","volume":"82","author":"W. T. Tutte","year":"1956","unstructured":"W.T. Tutte, \u201cA theorem on planar graphs\u201d, Trans. Amer. Math. Soc., Vol. 82, 1956, pp. 99\u2013116.","journal-title":"Trans. Amer. Math. Soc."},{"key":"8_CR11","doi-asserted-by":"crossref","first-page":"245","DOI":"10.2307\/2371127","volume":"55","author":"H. Whitney","year":"1933","unstructured":"H. Whitney, \u201c2-isomorphic graphs\u201d, Amer. J. Math., Vol. 55, 1933, pp. 245\u2013254.","journal-title":"Amer. J. Math."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56939-1_64","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:58:06Z","timestamp":1742594286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56939-1_64"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569398","9783540478263"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-56939-1_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"28 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}