Rainbow bases in matroids

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Rainbow bases in matroids

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Rainbow bases in matroids

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název periodika

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

1095-7146

Svazek periodika

38

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

20

Strana od-do

1472-1491

Kód UT WoS článku

001228166200003

EID výsledku v databázi Scopus

2-s2.0-85193826554