On acyclic colorings of direct products

Simon Špacapan; Aleksandra Tepeh Horvat

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 2, page 323-333
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Simon Špacapan, and Aleksandra Tepeh Horvat. "On acyclic colorings of direct products." Discussiones Mathematicae Graph Theory 28.2 (2008): 323-333. <http://eudml.org/doc/270706>.

@article{SimonŠpacapan2008,
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.},
author = {Simon Špacapan, Aleksandra Tepeh Horvat},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {coloring; acyclic coloring; distance-two coloring; direct product},
language = {eng},
number = {2},
pages = {323-333},
title = {On acyclic colorings of direct products},
url = {http://eudml.org/doc/270706},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Simon Špacapan
AU - Aleksandra Tepeh Horvat
TI - On acyclic colorings of direct products
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 2
SP - 323
EP - 333
AB - 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.
LA - eng
KW - coloring; acyclic coloring; distance-two coloring; direct product
UR - http://eudml.org/doc/270706
ER -

References

top
  1. [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. Zbl0735.05036
  2. [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. Zbl0857.05033
  3. [3] O.V. Borodin, On decomposition of graphs into degenerate subgraphs, Diskretny Analys, Novosibirsk 28 (1976) 3-12 (in Russian). Zbl0425.05058
  4. [4] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236, doi: 10.1016/0012-365X(79)90077-3. Zbl0406.05031
  5. [5] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390-412, doi: 10.1007/BF02764716. Zbl0265.05103
  6. [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. Zbl0664.05019
  7. [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. Zbl0575.05028
  8. [8] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000). 
  9. [9] R.E. Jamison and G.L. Matthews, Acyclic colorings of products of cycles, manuscript 2005. Zbl1181.05044
  10. [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. Zbl1184.05043
  11. [11] B. Mohar, Acyclic colorings of locally planar graphs, European J. Combin. 26 (2005) 491-503, doi: 10.1016/j.ejc.2003.12.016. Zbl1058.05024
  12. [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. Zbl1101.05035
  13. [13] X. Zhu, A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998) 1-24. Zbl0906.05024

NotesEmbed ?

top

You must be logged in to post comments.