Frustration index of a signed planar graph and the feedback vertex set

Abstract

A feedback vertex set of a graph is a set of vertices whose deletion leaves a forest. In 2016, Dross, Montassier, and Pinlou conjectured that every planar graph $G$ of girth at least $g$ admits a feedback vertex set of size at most $e(G)/g$. In this note, we confirm this conjecture by connecting this problem with signed graphs. The frustration index of a signed graph $(G,Σ)$ is defined as the minimum number of negative edges among all signatures on $G$ that are switching-equivalent to $Σ$. Equivalently, it is the minimum number of edges whose deletion results in a balanced subgraph of $(G,Σ)$. We show that the minimum size of a feedback vertex set of a planar graph is bounded above by the maximum frustration index over all signatures of the graph, and thereby provide a tight upper bound on the size of the minimum feedback vertex set, which resolves the conjecture of Dross, Montassier, and Pinlou (2016).

Disclosure

“Declaration of AI usage During the development and preparation of this manuscript, the authors used ChatGPT on a limited basis to explore possible approaches to selected parts of the mathematical arguments (namely, locating the relevant arguments and the proof of Lemma 3.5 in [15], and identifying the reference [12]), and to improve the language”

PDF page 9

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:59:16.056933Z

Structural counts