Structural characterization and efficient recognition of probe diamond-free graphs
A graph is probe diamond-free if its vertex set admits a partition into probes and nonprobes, where the set of nonprobes is independent, such that adding edges only between pairs of nonprobes yields a diamond-free graph. Although this class admits a characterization by forbidden induced subgraphs, such a characterization does not directly lead to an efficient recognition algorithm. In this work we introduce a new structural characterization of probe diamond-free graphs based on a local condition, called the \emph{locally union of complete split} property, together with an auxiliary bipartite…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.17080
curl -X POST /api/v1/records/arxiv/2605.17080/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.17080/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'