{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T19:54:14Z","timestamp":1770321254975,"version":"3.49.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,3,5]],"date-time":"2009-03-05T00:00:00Z","timestamp":1236211200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s00453-009-9295-2","type":"journal-article","created":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T20:01:52Z","timestamp":1236196912000},"page":"770-789","source":"Crossref","is-referenced-by-count":3,"title":["Fast 3-coloring Triangle-Free Planar Graphs"],"prefix":"10.1007","volume":"58","author":[{"given":"Lukasz","family":"Kowalik","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,3,5]]},"reference":[{"key":"9295_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1007\/978-3-540-30140-0_40","volume-title":"Proc. 12th Annual European Symposium on Algorithms (ESA 2004)","author":"\u0141. Kowalik","year":"2004","unstructured":"Kowalik, \u0141.: Fast 3-coloring triangle-free planar graphs. In: Albers, S., Radzik, T. (eds.) Proc. 12th Annual European Symposium on Algorithms (ESA 2004). Lecture Notes in Computer Science, vol.\u00a03221, pp.\u00a0436\u2013447. Springer, Berlin (2004)"},{"key":"9295_CR2","first-page":"571","volume-title":"Proc. 28th Symposium on Theory of Computing","author":"N. Robertson","year":"1996","unstructured":"Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: Proc. 28th Symposium on Theory of Computing, pp. 571\u2013575. ACM, New York (1996)"},{"key":"9295_CR3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0196-6774(81)90031-6","volume":"2","author":"N. Chiba","year":"1981","unstructured":"Chiba, N., Nishizeki, T., Saito, N.: A linear algorithm for five-coloring a planar graph. J. Algorithms 2, 317\u2013327 (1981)","journal-title":"J. Algorithms"},{"issue":"3","key":"9295_CR4","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., Johnson, D.S.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"9295_CR5","unstructured":"Gr\u00f6tzsch, H.: Ein dreifarbensatz fur dreikreisfreie netze auf der kuzel. Technical report, Wiss. Z. Martin Luther Univ. Halle Wittenberg, Math.-Nat. Reihe\u00a08 (1959)"},{"key":"9295_CR6","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1006\/jctb.1994.1069","volume":"62","author":"C. Thomassen","year":"1994","unstructured":"Thomassen, C.: Gr\u00f6tzsch\u2019s 3-color theorem and its counterparts for the torus and the projective plane. J. Comb. Theory, Ser. B 62, 268\u2013279 (1994)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9295_CR7","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0095-8956(03)00029-7","volume":"88","author":"C. Thomassen","year":"2003","unstructured":"Thomassen, C.: A short list color proof of Gr\u00f6tzsch\u2019s theorem. J. Comb. Theory, Ser. B 88, 189\u2013192 (2003)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"3","key":"9295_CR8","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1145\/1159892.1159895","volume":"2","author":"\u0141. Kowalik","year":"2006","unstructured":"Kowalik, \u0141., Kurowski, M.: Oracles for bounded-length shortest paths in planar graphs. ACM Trans. Algorithms 2(3), 335\u2013363 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"9295_CR9","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0095-8956(03)00025-X","volume":"88","author":"O.V. Borodin","year":"2003","unstructured":"Borodin, O.V., Raspaud, A.: A sufficient condition for planar graphs to be 3-colorable. J. Comb. Theory, Ser. B 88, 17\u201327 (2003)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9295_CR10","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.jctb.2004.11.001","volume":"93","author":"O.V. Borodin","year":"2005","unstructured":"Borodin, O.V., Glebov, A.N., Raspaud, A., Salavatipour, M.R.: Planar graphs without cycles of length from 4 to 7 are 3-colorable. J. Comb. Theory, Ser. B 93(2), 303\u2013311 (2005)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9295_CR11","series-title":"LNCS","first-page":"2","volume-title":"Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17\u201319, 2007, Proceedings","author":"Z. Dvorak","year":"2007","unstructured":"Dvorak, Z., Kr\u00e1l, D., Thomas, R.: Coloring triangle-free graphs on surfaces. In: Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17\u201319, 2007, Proceedings. LNCS, vol.\u00a04835, pp.\u00a02\u20134. Springer, Berlin (2007)"},{"key":"9295_CR12","volume-title":"Introduction to Graph Theory","author":"D. West","year":"1996","unstructured":"West, D.: Introduction to Graph Theory. Prentice Hall, New York (1996)"},{"issue":"11","key":"9295_CR13","doi-asserted-by":"crossref","first-page":"4555","DOI":"10.1090\/S0002-9947-97-01926-0","volume":"349","author":"J. Gimbel","year":"1997","unstructured":"Gimbel, J., Thomassen, C.: Coloring graphs with fixed genus and girth. Trans. Am. Math. Soc. 349(11), 4555\u20134564 (1997)","journal-title":"Trans. Am. Math. Soc."},{"key":"9295_CR14","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"9295_CR15","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/3-540-48447-7_34","volume-title":"Proc. 6th Int. Workshop on Algorithms and Data Structures","author":"G.S. Brodal","year":"1999","unstructured":"Brodal, G.S., Fagerberg, R.: Dynamic representations of sparse graphs. In: Proc. 6th Int. Workshop on Algorithms and Data Structures. LNCS, vol.\u00a01663, pp. 342\u2013351. Springer, Berlin (1999)"},{"key":"9295_CR16","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kawarabayashi, K., Thomas, R.: Three-coloring triangle-free planar graphs in linear time. In: SODA\u201909: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1176\u20131182 (2009)","DOI":"10.1137\/1.9781611973068.127"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9295-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9295-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9295-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:03Z","timestamp":1559137503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9295-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,5]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["9295"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9295-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,5]]}}}