# 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

## Access Full Article

top## Abstract

top## How to cite

topSimon Š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] 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] 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] O.V. Borodin, On decomposition of graphs into degenerate subgraphs, Diskretny Analys, Novosibirsk 28 (1976) 3-12 (in Russian). Zbl0425.05058
- [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] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390-412, doi: 10.1007/BF02764716. Zbl0265.05103
- [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] 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] 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. Zbl1181.05044
- [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] 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] 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] X. Zhu, A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998) 1-24. Zbl0906.05024

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.