The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnection denotes the maximum number of colors that can be used in a vertex coloring such that after deletion of the monochromatic arcs the graph is acyclic. Figueroa et al. generalized the definitions of a feedback arc set and the acyclic disconnection to undirected graphs. They proposed a connection between the two parameters in the undirected setting. To be more precise, they showed that in wheel graphs and grid graphs the sum of the two parameters equals the number of vertices and claimed it to be true for outerplanar graphs. We extend their results by giving a characterization of graph classes for which the directed version of the proposed relation holds, answering an open question of Figueroa et al. We apply our characterization to almost trees (3) and wheel graphs. Moreover, we show that the proposed relation does not hold for outerplanar graphs neither in the directed nor in the undirected version. This proves Theorem 15 of Figueroa et al. to be wrong. (c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).