On the Impossibility of Decomposing Binary Matroids
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 can be partitioned into sets X_1, X_2, …, X_l with the following two properties. Each set X_i has size at most ck. Moreover, for all sets Y such that |Y ∩ X_i| ≤ 1 it is the case that Y is b-colorable. A (b,c)-decomposition is a strict generalization of a partition decomposition and, thus, our result refutes a conjecture from arXiv:1911.10485v2 .
READ FULL TEXT