Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Acyclic coloring of special digraphs   An acyclic r-coloring of a directed graph G=(V,E) is a partition of the
vertex set V into r acyclic sets. The dichromatic number of a directed graph G
is the smallest r such that G allows an acyclic r-coloring. For symmetric
digraphs the dichromatic number equals the well-known chromatic number of the
underlying undirected graph. This allows us to carry over the W[1]-hardness and
lower bounds for running times of the chromatic number problem parameterized by
clique-width to the dichromatic number problem parameterized by directed
clique-width. We introduce the first polynomial-time algorithm for the acyclic
coloring problem on digraphs of constant directed clique-width. From a
parameterized point of view our algorithm shows that the Dichromatic Number
problem is in XP when parameterized by directed clique-width and extends the
only known structural parameterization by directed modular width for this
problem. Furthermore, we apply defineability within monadic second order logic
in order to show that Dichromatic Number problem is in FPT when parameterized
by the directed clique-width and r.
  For directed co-graphs, which is a class of digraphs of directed clique-width
2, and several generalizations we even show linear time solutions for computing
the dichromatic number. Furthermore, we conclude that directed co-graphs and
the considered generalizations lead to subclasses of perfect digraphs. For
directed cactus forests, which is a set of digraphs of directed tree-width 1,
we conclude an upper bound of 2 for the dichromatic number and we show that an
optimal acyclic coloring can be computed in linear time.

25
The categories of this paper are: patt-sol
6
The categories of this paper are: astro-ph
28
The categories of this paper are: alg-geom
14
The categories of this paper are: math-ph
21
The categories of this paper are: adap-org
22
The categories of this paper are: chao-dyn
23
The categories of this paper are: solv-int
12
The categories of this paper are: nucl-th
7
The categories of this paper are: hep-th
9
The categories of this paper are: nlin
35
The categories of this paper are: mtrl-th
31
The categories of this paper are: ao-sci
32
The categories of this paper are: atom-ph
30
The categories of this paper are: q-alg
0
The categories of this paper are: hep-ph
8
The categories of this paper are: hep-ex