Count matroids of group-labeled graphs
Combinatorica , Volume 38 p. 1101- 1127
A graph G = (V, E) is called (k, ℓ)-sparse if |F| ≤ k|V (F)| − ℓ for any nonempty F ⊆ E, where V (F) denotes the set of vertices incident to F. It is known that the family of the edge sets of (k, ℓ)-sparse subgraphs forms the family of independent sets of a matroid, called the (k, ℓ)-count matroid of G. In this paper we shall investigate lifts of the (k, ℓ)- count matroids by using group labelings on the edge set. By introducing a new notion called near-balancedness, we shall identify a new class of matroids whose independence condition is described as a count condition of the form |F| ≤ k|V (F)|−ℓ+αψ (F) for some function αψ determined by a given group labeling ψ on E.
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
Ikeshita, R, & Tanigawa, S.-I. (2017). Count matroids of group-labeled graphs. Combinatorica, 38, 1101–1127. doi:10.1007/s00493-016-3469-8