Basis Number of Graphs Excluding Minors
The basis number of a graph $G$ is the minimum $k$ such that the cycle space of $G$ is generated by a family of cycles using each edge at most $k$ times. A classical result of Mac Lane states that planar graphs are exactly graphs with basis number at most 2, and more generally, graphs embedded on a fixed surface of bounded genus are known to have bounded basis number. Generalising this, we prove that graphs excluding a fixed minor $H$ have bounded basis number. Our proof uses the Graph Minor Structure Theorem, which requires us to understand how basis number behaves in tree-decompositions.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.05195
curl -X POST /api/v1/records/arxiv/2601.05195/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.05195/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'