Discussiones Mathematicae Graph Theory 28(2) (2008) 323-333
doi: 10.7151/dmgt.1408

[BIBTex] [PDF] [PS]


Simon Spacapan

University of Maribor, FME
Smetanova 17, 2000 Maribor, Slovenia
e-mail: simon.spacapan@uni-mb.si

Aleksandra Tepeh Horvat

University of Maribor, FERI
Smetanova 17, 2000 Maribor, Slovenia
e-mail: aleksandra.tepeh@uni-mb.si


A coloring of a graph G is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees T1 and T2 equals min{Δ(T1)+1, Δ(T2)+1}. We also prove that the acyclic chromatic number of direct product of two complete graphs Km and Kn is mn−m−2, where m ≥ n ≥ 4. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.

Keywords: coloring, acyclic coloring, distance-two coloring, direct product.

2000 Mathematics Subject Classification: 05C15.


[1] N. Alon, C. McDiarmid and B. Reed, Acyclic colouring of graphs, Random Structures and Algorithms 2 (1991) 277-288, doi: 10.1002/rsa.3240020303.
[2] N. Alon, B. Mohar and D. P. Sanders, On acyclic colorings of graphs on surfaces, Israel J. Math. 94 (1996) 273-283, doi: 10.1007/BF02762708.
[3] O.V. Borodin, On decomposition of graphs into degenerate subgraphs, Diskretny Analys, Novosibirsk 28 (1976) 3-12 (in Russian).
[4] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236, doi: 10.1016/0012-365X(79)90077-3.
[5] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390-412, doi: 10.1007/BF02764716.
[6] D. Duffus, B. Sands and R.E. Woodrow, On the chromatic number of the product of graphs, J. Graph Theory 9 (1985) 487-495, doi: 10.1002/jgt.3190090409.
[7] M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica 5 (1985) 121-126, doi: 10.1007/BF02579374.
[8] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
[9] R.E. Jamison and G.L. Matthews, Acyclic colorings of products of cycles, manuscript 2005.
[10] R.E. Jamison, G.L. Matthews and J. Villalpando, Acyclic colorings of products of trees, Inform. Process. Lett. 99 (2006) 7-12, doi: 10.1016/j.ipl.2005.11.023.
[11] B. Mohar, Acyclic colorings of locally planar graphs, European J. Combin. 26 (2005) 491-503, doi: 10.1016/j.ejc.2003.12.016.
[12] C. Tardif, The fractional chromatic number of the categorical product of graphs, Combinatorica 25 (2005) 625-632, doi: 10.1007/s00493-005-0038-y.
[13] X. Zhu, A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998) 1-24.

Received 13 December 2007
Revised 18 February 2008
Accepted 20 February 2008