Title: The minimum feedback arc set problem and the acyclic disconnection for graphs
Abstract: 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.