Acyclic coloring of products of digraphs

The dichromatic number of a digraph G is the smallest integer χa(G) such that the vertex set of G can be partitioned into χa(G) sets, each of which induces an acyclic subdigraph. This is a generalization of the classic chromatic number of graphs. Here, we investigate the dichromatic number of the cartesian, direct, strong, and lexicographic products, generalizing some classic results on the chromatic number of products. More specifically, by letting □ denote the cartesian product, × the direct product, ⊠ the strong product, and G[H] the lexicographic product of G by H, we proved that the following inequalities, known to hold for the chromatic number of graphs, still hold for the dichromatic number of digraphs: χa(G□H)=max{χa(G),χa(H)}; χa(G×H)≤min{χa(G),χa(H)}; and χa(G[H])=χa(G[K↔k]), where k=χa(H) and K↔k denotes the complete digraph on k vertices. In addition, we investigate the products of directed cycles, giving exact values for χa(C→n×C→m) and χa(C→n⊠C→m) for every n,m, and for χa(C→n[H]) for every positive integer n. We also close the gap about the chromatic number of the strong product of a cycle by a bipartite graph, providing exact values for χ(Cn⊠H) when H is bipartite.