Geodesic
On acyclic colorings of direct products
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 2, pp. 323-333

Voir la notice de l'article provenant de la source Library of Science

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: coloring, acyclic coloring, distance-two coloring, direct product 
@article{DMGT_2008_28_2_a7,
     author = {\v{S}pacapan, Simon and Horvat, Aleksandra},
     title = {On acyclic colorings of direct products},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {323--333},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a7/}
}
TY  - JOUR
AU  - Špacapan, Simon
AU  - Horvat, Aleksandra
TI  - On acyclic colorings of direct products
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2008
SP  - 323
EP  - 333
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a7/
LA  - en
ID  - DMGT_2008_28_2_a7
ER  - 
%0 Journal Article
%A Špacapan, Simon
%A Horvat, Aleksandra
%T On acyclic colorings of direct products
%J Discussiones Mathematicae. Graph Theory
%D 2008
%P 323-333
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a7/
%G en
%F DMGT_2008_28_2_a7
Špacapan, Simon; Horvat, Aleksandra. On acyclic colorings of direct products. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 2, pp. 323-333. http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a7/