Graphic matroids with connectivity constraints
In 1959, Tutte proved that a matroid can be realised by a graph if and only if it does not have a minor isomorphic to $U_{2,4}$, $F_7$, $F_7^*$, $M^*(K_5)$ or $M^*(K_{3,3})$. In this paper, we extend this theorem to determine when it is possible to find a graphic realisation $G$ of a matroid $M$, subject to a list of additional constraints of the following form: a subset $F$ of the elements of $M$ must induce a connected subgraph of $G$. We prove that a connected matroid with such constraints---called a `constraint matroid'---is realisable as a graph satisfying those constraints if and only…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.01841
curl -X POST /api/v1/records/arxiv/2611.01841/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01841/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'