# 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.