























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. In particular, we prove that graphs of treewidth $k$ have basis number bounded by some function of $k$. We handle tree-decompositions using the proof framework developed by Bojańczyk and Pilipczuk in their proof of Courcelle's conjecture. Combining our approach with independent results of Miraftab, Morin and Yuditsky (2025) on basis number and path-decompositions, one can moreover improve our upper bound to a polynomial one: there exists an absolute constant $c>0$ such that every $H$-minor free graph has basis number $O(|H|^c)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。