The minimum feedback arc set problem and the acyclic disconnection for graphs

A minimum feedback arc set of a digraph D is a minimum set of arcs which removal leaves the resultant graph free of directed cycles; its cardinality is denoted by τ1(D). The acyclic disconnection of D, ω⃗(D), is defined as the maximum number of colors in a vertex coloring of D such that every directed cycle of D contains at least one monochromatic arc. In this article we study the relationship between the minimum feedback arc set and the acyclic disconnection of a digraph, we prove that the acyclic disconnection problem is NP-complete. We define the acyclic disconnection and the minimum feedback for graphs. We also prove that ω⃗(G)+τ1(G)=|V(G)| if G is a wheel, a grid or an outerplanar graph.