Rainbow bases in matroids

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F24%3A43974792" target="_blank" >RIV/49777513:23520/24:43974792 - isvavai.cz</a>
Result on the web
<a href="https://epubs.siam.org/doi/10.1137/22M1516750" target="_blank" >https://epubs.siam.org/doi/10.1137/22M1516750</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/22M1516750" target="_blank" >10.1137/22M1516750</a>

Result language
angličtina
Original language name
Rainbow bases in matroids
Original language description
Recently, it was proved by Bérczi and Schwarcz that the problem of factorizing a matroid into rainbow bases with respect to a given partition of its ground set is algorithmically intractable. On the other hand, many special cases were left open.We first show that the problem remains hard if the matroid is graphic, answering a question of Bérczi and Schwarcz. As another special case, we consider the problem of deciding whether a given digraph can be factorized into subgraphs which are spanning trees in the underlying sense and respect upper bounds on the indegree of every vertex. We prove that this problem is also hard. This answers a question of Frank.In the second part of the article, we deal with the relaxed problem of covering the ground set of a matroid by rainbow bases. Among other results, we show that there is a linear function f such that every matroid that can be factorized into k bases for some k≥3 can be covered by f(k) rainbow bases if every partition class contains at most 2 elements.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)