{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T01:20:35Z","timestamp":1777425635275,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,2,1]],"date-time":"2011-02-01T00:00:00Z","timestamp":1296518400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s10878-011-9385-3","type":"journal-article","created":{"date-parts":[[2011,1,31]],"date-time":"2011-01-31T14:42:51Z","timestamp":1296484971000},"page":"116-130","source":"Crossref","is-referenced-by-count":12,"title":["Acyclically 3-colorable planar graphs"],"prefix":"10.1007","volume":"24","author":[{"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[]},{"given":"Fabrizio","family":"Frati","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,2,1]]},"reference":[{"key":"9385_CR1","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/BF02764716","volume":"14","author":"MO Albertson","year":"1973","unstructured":"Albertson MO, Berman D (1973) Every planar graph has an acyclic 7-coloring. Isr J Math 14:390\u2013408","journal-title":"Isr J Math"},{"issue":"3","key":"9385_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/rsa.3240020303","volume":"2","author":"N Alon","year":"1991","unstructured":"Alon N, McDiarmid C, Reed BA (1991) Acyclic coloring of graphs. Random Struct Algorithms 2(3):277\u2013288","journal-title":"Random Struct Algorithms"},{"key":"9385_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/978-3-642-11440-3_11","volume-title":"Workshop on algorithms and computation (WALCOM \u201910)","author":"P Angelini","year":"2010","unstructured":"Angelini P, Frati F (2010) Acyclically 3-colorable planar graphs. In: Rahman MdS, Fujita S (eds) Workshop on algorithms and computation (WALCOM \u201910). LNCS, vol 5942, pp 113\u2013124"},{"issue":"3","key":"9385_CR4","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"K Appel","year":"1977","unstructured":"Appel K, Haken W (1977) Every planar map is 4-colorable. I. Discharging. Ill J Math 21(3):429\u2013490","journal-title":"Ill J Math"},{"issue":"3","key":"9385_CR5","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 (1977) Every planar map is 4-colorable. II. Reducibility. Ill J Math 21(3):491\u2013567","journal-title":"Ill J Math"},{"key":"9385_CR6","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0012-365X(79)90077-3","volume":"25","author":"OV Borodin","year":"1979","unstructured":"Borodin OV (1979) On acyclic colourings of planar graphs. Discrete Math 25:211\u2013236","journal-title":"Discrete Math"},{"issue":"2","key":"9385_CR7","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1112\/S0024610799007942","volume":"60","author":"OV Borodin","year":"1999","unstructured":"Borodin OV, Kostochka AV, Woodall DR (1999) Acyclic colourings of planar graphs with large girth. J Lond Math Soc 60(2):344\u2013352","journal-title":"J Lond Math Soc"},{"key":"9385_CR8","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brook","year":"1941","unstructured":"Brook RL (1941) On coloring the nodes of a network. Proc Camb Philos Soc 37:194\u2013197","journal-title":"Proc Camb Philos Soc"},{"issue":"2","key":"9385_CR9","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0607026","volume":"7","author":"F Coleman","year":"1986","unstructured":"Coleman F, Cai J-Y (1986) The cyclic coloring problem and estimation of sparse Hessian matrices. SIAM J Algebr Discrete Methods 7(2):221\u2013235","journal-title":"SIAM J Algebr Discrete Methods"},{"issue":"2","key":"9385_CR10","first-page":"497","volume":"6","author":"V Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107 V, P\u00f3r A, Wood DR (2004) Track layouts of graphs. Discrete Math Theor Comput Sci 6(2):497\u2013522","journal-title":"Discrete Math Theor Comput Sci"},{"issue":"3","key":"9385_CR11","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1137\/S0097539702416141","volume":"34","author":"V Dujmovi\u0107","year":"2005","unstructured":"Dujmovi\u0107 V, Morin P, Wood DR (2005) Layout of graphs with bounded tree-width. SIAM J Comput 34(3):553\u2013579","journal-title":"SIAM J Comput"},{"issue":"4","key":"9385_CR12","doi-asserted-by":"crossref","first-page":"363","DOI":"10.7155\/jgaa.00075","volume":"7","author":"S Felsner","year":"2003","unstructured":"Felsner S, Liotta G, Wismath SK (2003) Straight-line drawings on restricted integer grids in two and three dimensions. J Graph Algorithms Appl 7(4):363\u2013398","journal-title":"J Graph Algorithms Appl"},{"key":"9385_CR13","unstructured":"Gebremedhin AH, Manne F, Pothen A (2002) Graph coloring in optimization revisited. Technical Report 226, University of Bergen, Norway"},{"issue":"2","key":"9385_CR14","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/ijoc.1080.0286","volume":"21","author":"AH Gebremedhin","year":"2009","unstructured":"Gebremedhin AH, Tarafdar A, Pothen A, Walther A (2009) Efficient computation of sparse Hessians using coloring and automatic differentiation. INFORMS J Comput 21(2):209\u2013223","journal-title":"INFORMS J Comput"},{"key":"9385_CR15","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/BF02764716","volume":"14","author":"B Gr\u00fcnbaum","year":"1973","unstructured":"Gr\u00fcnbaum B (1973) Acyclic colorings of planar graphs. Isr J Math 14:390\u2013408","journal-title":"Isr J Math"},{"issue":"5","key":"9385_CR16","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1137\/0221055","volume":"21","author":"LS Heath","year":"1992","unstructured":"Heath LS, Rosenberg AL (1992) Laying out graphs using queues. SIAM J Comput 21(5):927\u2013958","journal-title":"SIAM J Comput"},{"issue":"3","key":"9385_CR17","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1137\/0405031","volume":"5","author":"LS Heath","year":"1992","unstructured":"Heath LS, Leighton FT, Rosenberg AL (1992) Comparing queues and stacks as mechanisms for laying out graphs. SIAM J Discrete Math 5(3):398\u2013412","journal-title":"SIAM J Discrete Math"},{"key":"9385_CR18","first-page":"40","volume":"28","author":"AV Kostochka","year":"1976","unstructured":"Kostochka AV (1976) Acyclic 6-coloring of planar graphs. Metody Diskret Anal 28:40\u201356","journal-title":"Metody Diskret Anal"},{"key":"9385_CR19","unstructured":"Kostochka AV (1978) Upper bounds of chromatic functions of graphs. PhD thesis, University of Novosibirsk (in Russian)"},{"key":"9385_CR20","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/0012-365X(76)90075-3","volume":"14","author":"AV Kostochka","year":"1976","unstructured":"Kostochka AV, Melnikov LS (1976) Note to the paper of B. Gr\u00fcnbaum on acyclic colorings. Discrete Math 14:403\u2013406","journal-title":"Discrete Math"},{"key":"9385_CR21","unstructured":"Lyons A (2009) Restricted coloring problems and forbidden induced subgraphs. Preprint ANL\/MCS-P1611-0409, Mathematics and Computer Science Division, Argonne National Laboratory"},{"key":"9385_CR22","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1215\/S0012-7094-74-04119-2","volume":"41","author":"J Mitchem","year":"1974","unstructured":"Mitchem J (1974) Every planar graph has an acyclic 8-coloring. Duke Math J 41:177\u2013181","journal-title":"Duke Math J"},{"key":"9385_CR23","series-title":"DMTCS","first-page":"357","volume-title":"European conference on combinatorics, graph theory and applications (EuroComb \u201905)","author":"P Ochem","year":"2005","unstructured":"Ochem P (2005) Negative results on acyclic improper colorings. In: Felsner S (ed) European conference on combinatorics, graph theory and applications (EuroComb \u201905). DMTCS, vol AE, pp 357\u2013362"},{"key":"9385_CR24","first-page":"571","volume-title":"ACM symposium on theory of computing (STOC \u201996)","author":"N Robertson","year":"1996","unstructured":"Robertson N, Sanders DP, Seymour PD, Thomas R (1996) Efficiently four-coloring planar graphs. In: ACM symposium on theory of computing (STOC \u201996), pp 571\u2013575"},{"issue":"4","key":"9385_CR25","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/j.ipl.2004.08.002","volume":"92","author":"S Skulrattanakulchai","year":"2004","unstructured":"Skulrattanakulchai S (2004) Acyclic colorings of subcubic graphs. Inf Process Lett 92(4):161\u2013167","journal-title":"Inf Process Lett"},{"issue":"2","key":"9385_CR26","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes J, Tarjan RE, Lawler EL (1982) The recognition of series parallel digraphs. SIAM J Comput 11(2):298\u2013313","journal-title":"SIAM J Comput"},{"issue":"1","key":"9385_CR27","first-page":"37","volume":"7","author":"DR Wood","year":"2005","unstructured":"Wood DR (2005) Acyclic, star and oriented colourings of graph subdivisions. Discrete Math Theor Comput Sci 7(1):37\u201350","journal-title":"Discrete Math Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-011-9385-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-011-9385-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-011-9385-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T03:07:33Z","timestamp":1559963253000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-011-9385-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,1]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9385"],"URL":"https:\/\/doi.org\/10.1007\/s10878-011-9385-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,1]]}}}