2017-08-14
Count matroids of group-labeled graphs
Publication
Publication
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.
Additional Metadata | |
---|---|
doi.org/10.1007/s00493-016-3469-8 | |
Combinatorica | |
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
|