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 tau(1)(D). The acyclic disconnection of D, (omega) over right arrow (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 (omega) over right arrow (G)+ tau(1)(G) |V(G)| if G is a wheel, a grid or an outerplanar graph. (C) 2017 Elsevier B.V. All rights reserved.