On the Impossibility of Decomposing Binary Matroids

DOI10.1016/J.ORL.2022.09.003MaRDI QIDQ6403177arXivFDO

Authors Marilena Leichter, Benjamin Moseley, Kirk Pruhs

Publication date 26 June 2022

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2022.09.003

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

arXiv classification

cs.DSmath.CO

Abstract: 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,ldots,X_l$ with the following two properties. Each set $X_i$ has size at most $ck$. Moreover, for all sets $Y$ such that $|Ycap{X}_i|leq1$ 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 .

This page was built for publication: On the Impossibility of Decomposing Binary Matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403177)