Bounding the acyclic chromatic number for graphs of bounded degree
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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\) edgedisjoint 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), 5169.

2  N. Alon, C. McDiarmid and B. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2 (1991), 277288. 
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), 1820. 
4  O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979), 211236. 
5  P. Erdös, Some recent problems and results in graph theory, Discrete Math. 164 (1997), 8185. 
6  B. Grunbaum, Acyclic colorings of planar graphs, Isr. J. Math. 14 (1973), 390412. 