Basis Number and Pathwidth
We prove two results relating the basis number of a graph $G$ to path decompositions of $G$. Our first result shows that the basis number of a graph is at most four times its pathwidth. Our second result shows that, if a graph $G$ has a path decomposition with adhesions of size at most $k$ in which the graph induced by each bag has basis number at most $b$, then $G$ has basis number at most $b+O(k\log^2 k)$. The first result, combined with recent work of Geniet and Giocanti shows that the basis number of a graph is bounded by a polynomial function of its treewidth. The second result (also…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.14095
curl -X POST /api/v1/records/arxiv/2601.14095/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.14095/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'