On the Impossibility of Decomposing Binary Matroids

Marilena Leichter, Benjamin Moseley, Kirk Pruhs

We show that there exist $k$-colorable matroids that are not $(b,c)$-decomposable when $b$ and $c$ are constants. A matroid is $(b,c)$-decomposable, if its ground set of elements c…