ACYCLIC COLORINGS OF GRAPHS WITH OBSTRUCTIONS

Given a graph G, a coloring of G is acyclic if it is a proper coloring of G and every cycle contains at least three colors. Its acyclic chromatic number \chia(G) is the minimum k such that an acyclic k-coloring of G exists. When G has maximum degree \Delta , it is known that \chia(G) = Q(\Delta4/3) as \Delta- oo and that \chia(G) = Q(root t \cdot \Delta ) if, in addition, G does not contain K2,t as a subgraph. We study the extremal value of the acyclic chromatic number in the class of graphs of maximum degree is at most Q(t8/3\Delta2/3) if F is a tree, Q(root t \cdot \Delta ) if F is bipartite and can be made acyclic with the \Delta that do not contain some fixed subgraph F on t vertices. We establish that this extremal value removal of one vertex, 2\Delta + Q(t\Delta2/3) if F is an even cycle of length at least 6, and Q(t1/4\Delta5/4) if F = K3,t. Moreover, we exhibit an infinite family of obstructions F that each induces a different asymptotic behavior for this extremal value. This is obtained with the derivation of lower bounds that come from the analysis of the acyclic chromatic number of a random graph drawn from either G(n, p) or G(n, n, p), which we entirely determine up to a polylog(n) factor. As a byproduct, we can certify that most of our results are tight up to a \DeltaO(1/t) factor.