Flips and Merge-Width in Sparse Graphs
A flip of a graph is obtained by complementing the edge relation within a set of vertices. Flips are typically used to separate vertices in a graph, by increasing the distances between them. We show that in $K_{t,t}$-free graphs, every short sequence of flips can be simulated by a short sequence of vertex deletions that achieves a similar degree of separation: distances in the resulting graph are, up to a factor of three, at least as large as those obtained after the flips. This result provides a simple and uniform explanation of an emerging pattern in structural graph theory and finite…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.12926
curl -X POST /api/v1/records/arxiv/2602.12926/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.12926/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'