Coloração acíclica de produto de digrafos e digrafos com largura em árvore limitada

Abstract

In this work, a digraph coloring is studied. The acyclic chromatic number of a digraph G is the least integer χ a (G) such that the vertex set of G can be partitioned into χ a (G) sets each of which induces an acyclic subdigraph. Two topics are addressed on the acyclic chromatic number. In the first, we investigate the acyclic chromatic number of the cartesian, direct, strong and lexicographic products. We prove some results for each of these products. We show that que acyclic chromatic number of the cartesian product, G □ H, is equal to max{χ a (G), χ a (H)}. Also, we showed that the direct product of a finite number of oriented cycles has acyclic chromatic number equals 2. Furthermore, still about the cycles, we establish exact values for the acyclic chromatic number of the strong product of two oriented cycles. And finishing the product topic, we establish exact values for the lexicographic product C n [H] of a oriented cycle on n vertices by an arbitray digraph H such that n ≤ χ a (H) completing the result given in Pleanmani and Panma (2016). In the second topic, we prove that ⌈ tw+12⌉ is an upper bound for the acyclic chromatic number of a oriented graph that has treewidth at most tw and give an FPT algorithm to compute the chromatic number of bounded-treewidth digraphs is given.