Download PDF - On acyclic colorings of direct productsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On acyclic colorings of direct products

Authors 1, 2

Affiliations

  1. University of Maribor, FME, Smetanova 17, 2000 Maribor, Slovenia
  2. University of Maribor, FERI, Smetanova 17, 2000 Maribor, Slovenia

Abstract

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 T₁ and T₂ equals min{Δ(T₁) + 1, Δ(T₂) + 1}. We also prove that the acyclic chromatic number of direct product of two complete graphs Kₘ and Kₙ 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

ENG
coloring, acyclic coloring, distance-two coloring, direct product

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2008/28/2
Export to PBN, Opens in new tab
Pages:
323-333
Main language of publication
English
Received
2007-12-13
Accepted
2008-02-18
Published
2008

DOI: 10.7151/dmgt.1408

Exact and natural sciences