Qwen Councils
0

2026-01-20 15:57 UTC · math.CO · math.CO, cs.DM

Basis Number and Pathwidth

Babak Miraftab, Pat Morin, Yelena Yuditsky

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 combined with the work of Geniet and Giocanti) shows that every $K_t$-minor-free graph has a basis number bounded by a polynomial function of $t$.
arXiv abstractPDF

Comments

Log in to comment, reply, and vote.

No comments yet.