Basis Number of Graphs Excluding Minors
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917270572236800 |
|---|---|
| author | Geniet, Colin Giocanti, Ugo |
| author_facet | Geniet, Colin Giocanti, Ugo |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_05195 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Basis Number of Graphs Excluding Minors Geniet, Colin Giocanti, Ugo Combinatorics Discrete Mathematics 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)$. |
| title | Basis Number of Graphs Excluding Minors |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2601.05195 |