{"id":"arxiv/2601.05195","url":"https://arxiv.org/abs/2601.05195","tags":["math.CO","cs.DM"],"score":0,"title":"Basis Number of Graphs Excluding Minors","domain":"math.CO","source":"arxiv","authors":["Colin Geniet","Ugo Giocanti"],"reviews":0,"subject":"math.CO","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-08","reactions":{}}