Bounding the acyclic chromatic number for graphs of bounded degree

A vertex coloring of a graph \( G\) is said to be acyclic if no two adjacent vertices have the same color and there is no cycle involving vertices in two colors. The acyclic chromatic number of a graph \( G\) is the minimum number of colors in an acyclic coloring of \( G\). Grunbaum [6] first introduced acyclic colorings and he conjectured that any planar graph has an acyclic coloring in \( 5\) colors. This conjecture was proved by Borodin [3] [4]. Erdös considered acyclic colorings for graphs with bounded maximum degree and he asked :

Problem

How large can the acyclic chromatic number be for graphs with maximum degree \(d\)?

Let \( f(d)\) denote the maximum acyclic chromatic number over all graphs with maximum degree \( d\). Erdös [1] showed that \( f(d) \geq d^{4/3-\epsilon}\). Alon, McDiarmid and Reed [2] showed by probabilistic methods that

\(\displaystyle c \frac{ d^{4/3}}{(\log d)^{1/3}} < f(d) < c d^{4/3}. \)

Erdös and Hajnal [5] raised the following two interesting questions:

Problem

Is it true that for every \(k\), there is an \(f(k)\) so that if a graph \(G\) has chromatic number at least \(f(k)\), then it always contains an odd cycle whose vertices span a graph of chromatic number at least \(k\)?

Problem

Is it true that for every \(k\), there is an \(F(k)\) so that if a graph \(G\) has chromatic number at least \(F(k)\), then it always contains \(k\) edge-disjoint cycles on the same set of vertices?

Bibliography
1 M. O. Albertson and D. M. Berman, The acyclic chromatic number, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, XVII (1976), 51-69.

2 N. Alon, C. McDiarmid and B. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2 (1991), 277-288.

3 O. V. Borodin, A proof of B. Brunbaum's conjecture on the acyclic \( 5\)-colorability of planar graphs, Dokl. Akad. Nauk. SSSR 231 (1976), 18-20.

4 O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979), 211-236.

5 P. Erdös, Some recent problems and results in graph theory, Discrete Math. 164 (1997), 81-85.

6 B. Grunbaum, Acyclic colorings of planar graphs, Isr. J. Math. 14 (1973), 390-412.