{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T08:57:48Z","timestamp":1770541068647,"version":"3.49.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"S1","license":[{"start":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T00:00:00Z","timestamp":1663718400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T00:00:00Z","timestamp":1663718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00493-022-4891-8","type":"journal-article","created":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T18:02:47Z","timestamp":1663783367000},"page":"1081-1098","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Decidability of Hyperbolicity"],"prefix":"10.1007","volume":"42","author":[{"given":"Zden\u011bk","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[]},{"given":"Luke","family":"Postle","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,21]]},"reference":[{"key":"4891_CR1","first-page":"429","volume":"21","author":"K Appel","year":"1977","unstructured":"K. Appel and W. Haken: Every planar map is four colorable, Part I: Discharging, Illinois J. of Math. 21 (1977), 429\u2013490.","journal-title":"Illinois J. of Math."},{"key":"4891_CR2","first-page":"491","volume":"21","author":"K Appel","year":"1977","unstructured":"K. Appel, W. Haken and J. Koch: Every planar map is four colorable, Part II: Reducibility, Illinois J. of Math. 21 (1977), 491\u2013567.","journal-title":"Illinois J. of Math."},{"key":"4891_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0012-365X(79)90077-3","volume":"25","author":"O Borodin","year":"1979","unstructured":"O. Borodin: On acyclic colorings of planar graphs, Discrete Mathematics 25 (1979), 211\u2013236.","journal-title":"Discrete Mathematics"},{"key":"4891_CR4","unstructured":"Z. Dvo\u0159\u00e1k and K. Kawarabayashi: Choosability of planar graphs of girth 5, arXiv:1109.2976 (2011)."},{"key":"4891_CR5","doi-asserted-by":"crossref","unstructured":"Z. Dvo\u0159\u00e1k and K. Kawarabayashi: List-coloring embedded graphs, in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6\u20138, 2013, SIAM, 2013, 1004\u20131012.","DOI":"10.1137\/1.9781611973105.72"},{"key":"4891_CR6","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/j.jctb.2020.06.005","volume":"145","author":"Z Dvo\u0159\u00e1k","year":"2020","unstructured":"Z. Dvo\u0159\u00e1k, D. Kr\u00e1l\u2019 and R. Thomas: Three-coloring triangle-free graphs on surfaces III. Graphs of girth five, Journal of Combinatorial Theory, Series B 145 (2020), 376\u2013432.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4891_CR7","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/j.jctb.2016.06.006","volume":"122","author":"Z Dvo\u0159\u00e1k","year":"2017","unstructured":"Z. Dvo\u0159\u00e1k, B. Lidick\u00fd, B. Mohar and L. Postle: 5-list-coloring planar graphs with distant precolored vertices, Journal of Combinatorial Theory, Series B 122 (2017), 311\u2013352.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4891_CR8","doi-asserted-by":"publisher","first-page":"1746","DOI":"10.1137\/11082703X","volume":"25","author":"Z Dvo\u0159\u00e1k","year":"2011","unstructured":"Z. Dvo\u0159\u00e1k, B. Lidick\u00fd and R. \u0160krekovski: Graphs with two crossings are 5-choosable, SIAM J. Discrete Math. 25 (2011), 1746\u20131753.","journal-title":"SIAM J. Discrete Math."},{"key":"4891_CR9","first-page":"265","volume":"8","author":"T Gallai","year":"1963","unstructured":"T. Gallai: Kritische Graphen I, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 265\u2013292.","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"4891_CR10","first-page":"109","volume":"8","author":"H Gr\u00f6tzsch","year":"1959","unstructured":"H. Gr\u00f6tzsch: Ein Dreifarbensatz f\u00fcr dreikreisfreie Netze auf der Kugel, Math.-Natur. Reihe 8 (1959), 109\u2013120.","journal-title":"Math.-Natur. Reihe"},{"key":"4891_CR11","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R Lipton","year":"1979","unstructured":"R. Lipton and R. Tarjan: A separator theorem for planar graphs, SIAM Journal on Applied Mathematics 36 (1979), 177\u2013189.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"4891_CR12","unstructured":"L. Postle: 5-List-Coloring Graphs on Surfaces, PhD thesis, Georgia Institute of Technology, 2012."},{"key":"4891_CR13","doi-asserted-by":"crossref","unstructured":"L. Postle: Linear-time and efficient distributed algorithms for list coloring graphs on surfaces, in: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2019, 929\u2013941.","DOI":"10.1109\/FOCS.2019.00060"},{"key":"4891_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jctb.2020.09.013","volume":"147","author":"L Postle","year":"2021","unstructured":"L. Postle: 3-list-coloring graphs of girth at least five on surfaces, Journal of Combinatorial Theory, Series B 147 (2021), 1\u201336.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4891_CR15","unstructured":"L. Postle and R. Thomas: A Linear Upper Bound for 6-Critical Graphs on Surfaces, manuscript."},{"key":"4891_CR16","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.jctb.2015.12.005","volume":"119","author":"L Postle","year":"2016","unstructured":"L. Postle and R. Thomas: Five-list-coloring graphs on surfaces II. A linear bound for critical graphs in a disk, J. Comb. Theory, Ser. B 119 (2016), 42\u201365.","journal-title":"J. Comb. Theory, Ser. B"},{"key":"4891_CR17","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1090\/btran\/26","volume":"5","author":"L Postle","year":"2018","unstructured":"L. Postle and R. Thomas: Hyperbolic families and coloring graphs on surfaces, Transactions of the American Mathematical Society, Series B 5 (2018), 167\u2013221.","journal-title":"Transactions of the American Mathematical Society, Series B"},{"key":"4891_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N Robertson","year":"1997","unstructured":"N. Robertson, D. P. Sanders, P. Seymour and R. Thomas: The four colour theorem, J. Combin. Theory, Ser. B 70 (1997), 2\u201344.","journal-title":"J. Combin. Theory, Ser. B"},{"key":"4891_CR19","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jctb.1994.1062","volume":"62","author":"C Thomassen","year":"1994","unstructured":"C. Thomassen: Every planar graph is 5-choosable, J. Combin. Theory, Ser. B 62 (1994), 180\u2013181.","journal-title":"J. Combin. Theory, Ser. B"},{"key":"4891_CR20","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/jctb.1995.1027","volume":"64","author":"C Thomassen","year":"1995","unstructured":"C. Thomassen: 3-list-coloring planar graphs of girth 5, J. Combin. Theory, Ser. B 64 (1995), 101\u2013107.","journal-title":"J. Combin. Theory, Ser. B"},{"key":"4891_CR21","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1016\/j.jctb.2006.09.002","volume":"97","author":"C Thomassen","year":"2007","unstructured":"C. Thomassen: Exponentially many 5-list-colorings of planar graphs, J. Combin. Theory, Ser. B 97 (2007), 571\u2013583.","journal-title":"J. Combin. Theory, Ser. B"},{"key":"4891_CR22","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/j.jctb.2018.06.004","volume":"134","author":"X Zhu","year":"2019","unstructured":"X. Zhu: The Alon-Tarsi number of planar graphs, J. Comb. Theory, Ser. B 134 (2019), 354\u2013358.","journal-title":"J. Comb. Theory, Ser. B"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-022-4891-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-022-4891-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-022-4891-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T16:31:57Z","timestamp":1675355517000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-022-4891-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,21]]},"references-count":22,"journal-issue":{"issue":"S1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["4891"],"URL":"https:\/\/doi.org\/10.1007\/s00493-022-4891-8","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,21]]},"assertion":[{"value":"24 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}