Frustration index of a signed planar graph and the feedback vertex set
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.17983
curl -X POST /api/v1/records/arxiv/2607.17983/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.17983/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'