{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:49Z","timestamp":1759637749098,"version":"3.41.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319295152"},{"type":"electronic","value":"9783319295169"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-29516-9_9","type":"book-chapter","created":{"date-parts":[[2016,2,19]],"date-time":"2016-02-19T05:05:19Z","timestamp":1455858319000},"page":"100-111","source":"Crossref","is-referenced-by-count":1,"title":["Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs"],"prefix":"10.1007","author":[{"given":"Konrad K.","family":"Dabrowski","sequence":"first","affiliation":[]},{"given":"Fran\u00e7ois","family":"Dross","sequence":"additional","affiliation":[]},{"given":"Matthew","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,2,20]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01204715","volume":"12","author":"N Alon","year":"1992","unstructured":"Alon, N., Tarsi, M.: Colorings and orientations of graphs. Combinatorica 12, 125\u2013134 (1992)","journal-title":"Combinatorica"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Appel, K., Haken, W.: Every planar map is four colorable, Contemporary Mathematics 89, AMS Bookstore (1989)","DOI":"10.1090\/conm\/098"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc. 37, 194\u2013197 (1941)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/j.disc.2011.09.028","volume":"312","author":"M Chen","year":"2012","unstructured":"Chen, M., Montassier, M., Raspaud, A.: Some structural properties of planar graphs and their applications to 3-choosability. Discrete Math. 312, 362\u2013373 (2012)","journal-title":"Discrete Math."},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"1960","DOI":"10.1016\/j.dam.2006.03.014","volume":"154","author":"M Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Hard coloring problems in low degree planar bipartite graphs. Discrete Appl. Math. 154, 1960\u20131965 (2006)","journal-title":"Discrete Appl. Math."},{"key":"9_CR6","first-page":"291","volume":"IV","author":"M Chudnovsky","year":"2014","unstructured":"Chudnovsky, M.: Coloring graphs with forbidden induced subgraphs. Proc. ICM IV, 291\u2013302 (2014)","journal-title":"Proc. ICM"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"5899","DOI":"10.1016\/j.disc.2009.04.010","volume":"309","author":"Z Dvo\u0159\u00e1k","year":"2009","unstructured":"Dvo\u0159\u00e1k, Z., Lidick\u00fd, B., \u0160krekovski, R.: Planar graphs without 3-, 7-, and 8-cycles are 3-choosable. Discrete Math. 309, 5899\u20135904 (2009)","journal-title":"Discrete Math."},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1017\/S0963548398003678","volume":"7","author":"T Emden-Weinert","year":"1998","unstructured":"Emden-Weinert, T., Hougardy, S., Kreuter, B.: Uniquely colourable graphs and the hardness of colouring graphs of large girth. Comb. Probab. Comput. 7, 375\u2013386 (1998)","journal-title":"Comb. Probab. Comput."},{"key":"9_CR9","unstructured":"Erd\u0151s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, pp. 125\u2013157. Winnipeg, Man., Utilitas Math. (1980)"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified $${\\sf NP}$$ -complete graph problems. In: Proceedings of STOC, pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.ipl.2012.12.003","volume":"113","author":"PA Golovach","year":"2013","unstructured":"Golovach, P.A., Heggernes, P., van \u2019t Hof, P., Paulusma, D.: Choosability on $$H$$ -free graphs. Inform. Process. Lett. 113, 107\u2013110 (2013)","journal-title":"Inform. Process. Lett."},{"key":"9_CR12","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of colouring graphs with forbidden subgraphs, Manuscript, arXiv:1407.1482v4 (2014)"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0012-365X(95)00104-5","volume":"159","author":"S Gutner","year":"1996","unstructured":"Gutner, S.: The complexity of planar graph choosability. Discrete Math. 159, 119\u2013130 (1996)","journal-title":"Discrete Math."},{"key":"9_CR14","first-page":"139","volume":"62","author":"J Kratochv\u00edl","year":"1993","unstructured":"Kratochv\u00edl, J.: Precoloring extension with fixed color bound. Acta Mathematica Universitatis Comenianae 62, 139\u2013153 (1993)","journal-title":"Acta Mathematica Universitatis Comenianae"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0166-218X(94)90150-3","volume":"50","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Tuza, Z.: Algorithmic complexity of list colourings. Discrete Appl. Math. 50, 297\u2013302 (1994)","journal-title":"Discrete Appl. Math."},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1006\/jctb.1998.1893","volume":"76","author":"PCB Lam","year":"1999","unstructured":"Lam, P.C.B., Xu, B., Liu, J.: The 4-choosability of plane graphs without 4-cycles. J. Comb. Theory Ser. B 76, 117\u2013126 (1999)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jctb.2014.06.004","volume":"109","author":"M Molloy","year":"2014","unstructured":"Molloy, M., Reed, B.: Colouring graphs when the number of colours is almost the maximum degree. J. Comb. Theory Ser. B 109, 134\u2013195 (2014)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.ipl.2005.10.014","volume":"99","author":"M Montassier","year":"2006","unstructured":"Montassier, M.: A note on the not 3-choosability of some families of planar graphs. Inform. Process. Lett. 99, 68\u201371 (2006)","journal-title":"Inform. Process. Lett."},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1016\/j.disc.2006.02.001","volume":"306","author":"M Montassier","year":"2006","unstructured":"Montassier, M., Raspaud, A., Wang, W.: Bordeaux 3-color conjecture and 3-choosability. Discrete Math. 306, 573\u2013579 (2006)","journal-title":"Discrete Math."},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jctb.1994.1062","volume":"62","author":"C Thomassen","year":"1994","unstructured":"Thomassen, C.: Every planar graph is $$5$$ -choosable. J. Comb. Theory Ser. B 62, 180\u2013181 (1994)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/jctb.1995.1027","volume":"64","author":"C Thomassen","year":"1995","unstructured":"Thomassen, C.: 3-List-coloring planar graphs of girth 5. J. Comb. Theory Ser. B 64, 101\u2013107 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR22","unstructured":"Vizing, V.G.: Coloring the vertices of a graph in prescribed colors. In: Diskret. Analiz., no. 29, Metody Diskret. Anal. v. Teorii Kodov i Shem, vol. 101, pp. 3\u201310 (1976)"},{"key":"9_CR23","first-page":"3","volume":"29","author":"VG Vizing","year":"1976","unstructured":"Vizing, V.G.: Vertex colorings with given colors. Diskret. Analiz. 29, 3\u201310 (1976)","journal-title":"Diskret. Analiz."},{"key":"9_CR24","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0012-365X(93)90579-I","volume":"120","author":"M Voigt","year":"1993","unstructured":"Voigt, M.: List colourings of planar graphs. Discrete Math. 120, 215\u2013219 (1993)","journal-title":"Discrete Math."},{"key":"9_CR25","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0012-365X(94)00180-9","volume":"146","author":"M Voigt","year":"1995","unstructured":"Voigt, M.: A not 3-choosable planar graph without 3-cycles. Discrete Math. 146, 325\u2013328 (1995)","journal-title":"Discrete Math."},{"key":"9_CR26","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1016\/j.disc.2005.11.041","volume":"307","author":"M Voigt","year":"2007","unstructured":"Voigt, M.: A non-3-choosable planar graph without cycles of length 4 and 5. Discrete Math. 307, 1013\u20131015 (2007)","journal-title":"Discrete Math."},{"key":"9_CR27","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.disc.2009.08.005","volume":"310","author":"Y Wang","year":"2010","unstructured":"Wang, Y., Lu, H., Chen, M.: Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable. Discrete Math. 310, 147\u2013158 (2010)","journal-title":"Discrete Math."},{"key":"9_CR28","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.dam.2010.11.002","volume":"159","author":"Y Wang","year":"2011","unstructured":"Wang, Y., Lu, H., Chen, M.: Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable. Discrete Appl. Math. 159, 232\u2013239 (2011)","journal-title":"Discrete Appl. Math."},{"key":"9_CR29","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.ipl.2008.04.004","volume":"108","author":"D-Q Wang","year":"2008","unstructured":"Wang, D.-Q., Wen, Y.-P., Wang, K.-L.: A smaller planar graph without 4-, 5-cycles and intersecting triangles that is not 3-choosable. Inform. Process. Lett. 108, 87\u201389 (2008)","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-29516-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T12:37:31Z","timestamp":1748781451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-29516-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319295152","9783319295169"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-29516-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}