On the complexity of packing rainbow spanning trees

DOI10.1016/J.DISC.2022.113297OpenAlexW4313549392MaRDI QIDQ2685331FDOQ2685331

Tamás Király, Kristóf Bérczi, Gergely Csáji

Publication date: 21 February 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2206.11924

Recommendations

• On packing spanning arborescences with matroid constraint
• Spanning trees with many or few colors in edge-colored graphs
• On packing spanning arborescences with matroid constraint
• Complexity of packing common bases in matroids
• On the tractability of some natural packing, covering and partitioning problems

zbMATH Keywords

complexitymatroidspacking problemsrainbow spanning treescommon basescommon spanning sets

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Problem of Decomposing a Graph into n Connected Factors
• Transversals and matroid partition
• Title not available (Why is that?)
• Title not available (Why is that?)
• Edge-disjoint rainbow spanning trees in complete graphs
• Rainbow spanning trees in complete graphs colored by one‐factorizations
• Edge-Disjoint Isomorphic Multicolored Trees and Cycles in Complete Graphs
• Multicolored trees in complete graphs
• Multicolored trees in complete graphs
• Title not available (Why is that?)
• Complexity of Matroid Property Algorithms
• On the number of rainbow spanning trees in edge-colored complete graphs
• The intersection of a matroid and a simplicial complex
• XSAT and NAE-SAT of linear CNF classes
• The edge covering number of the intersection of two matroids
• On Disjoint Common Bases in Two Matroids
• Linearly many rainbow trees in properly edge-coloured complete graphs
• Decompositions into spanning rainbow structures
• On Rota's Basis Conjecture
• Complexity of packing common bases in matroids
• A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory
• Decompositions into isomorphic rainbow spanning trees
• Rainbow and monochromatic circuits and cocircuits in binary matroids

Cited In (3)

• Diverse collections in matroids and graphs
• On the complexity of packing rainbow spanning trees
• The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties

This page was built for publication: On the complexity of packing rainbow spanning trees

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