{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T12:39:33Z","timestamp":1773319173866,"version":"3.50.1"},"reference-count":11,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,7,5]],"date-time":"2007-07-05T00:00:00Z","timestamp":1183593600000},"content-version":"vor","delay-in-days":5786,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1991,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A vertex coloring of a graph G is called <jats:italic>acyclic<\/jats:italic> if no two adjacent vertices have the same color and there is no two\u2010colored cycle in G. The <jats:italic>acyclic chromatic number<\/jats:italic> of G, denoted by <jats:italic>A(G)<\/jats:italic>, is the least number of colors in an acyclic coloring of G. We show that if G has maximum degree <jats:italic>d<\/jats:italic>, then <jats:italic>A(G) = 0(d<\/jats:italic><jats:sup>4\/3<\/jats:sup><jats:italic>)<\/jats:italic> as <jats:italic>d<\/jats:italic> \u2192 \u221e. This settles a problem of Erd\u00f6s who conjectured, in 1976, that <jats:italic>A(G) = o(d<\/jats:italic><jats:sup>2<\/jats:sup><jats:italic>)<\/jats:italic> as <jats:italic>d<\/jats:italic> \u2192 \u221e. We also show that there are graphs G with maximum degree <jats:italic>d<\/jats:italic> for which <jats:italic>A(G)<\/jats:italic> = \u03a9(d<jats:sup>4\/3<\/jats:sup>\/(log <jats:italic>d)<\/jats:italic><jats:sup>1\/3<\/jats:sup><jats:italic>);<\/jats:italic> and that the <jats:italic>edges<\/jats:italic> of any graph with maximum degree <jats:italic>d<\/jats:italic> can be colored by <jats:italic>0(d)<\/jats:italic> colors so that no two adjacent edges have the same color and there is no two\u2010colored cycle. All the proofs rely heavily on probabilistic arguments.<\/jats:p>","DOI":"10.1002\/rsa.3240020303","type":"journal-article","created":{"date-parts":[[2010,7,12]],"date-time":"2010-07-12T07:58:05Z","timestamp":1278921485000},"page":"277-288","source":"Crossref","is-referenced-by-count":174,"title":["Acyclic coloring of graphs"],"prefix":"10.1002","volume":"2","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Colin","family":"Mcdiarmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruce","family":"Reed","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,7,5]]},"reference":[{"key":"e_1_2_1_1_2","first-page":"51","volume-title":"The acyclic chromatic number, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing","author":"Albertson M. O.","year":"1976"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02783300"},{"key":"e_1_2_1_3_2","author":"Alon N.","journal-title":"Star arboricity"},{"key":"e_1_2_1_4_2","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","year":"1985"},{"key":"e_1_2_1_5_2","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s B.","year":"1978"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90077-3"},{"key":"e_1_2_1_7_2","volume-title":"Infinite and Finite Sets","author":"Erd\u014ds P.","year":"1975"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02764716"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0060851"},{"key":"e_1_2_1_10_2","volume-title":"Ten Lectures on the Probabilistic Method","author":"Spencer J.","year":"1987"},{"key":"e_1_2_1_11_2","series-title":"Pitman Research Notes in Mathematics Series 218","first-page":"9","volume-title":"Graph Colorings","author":"Toft B.","year":"1990"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240020303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240020303","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240020303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T23:06:59Z","timestamp":1698016019000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240020303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["10.1002\/rsa.3240020303"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240020303","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}