On the complexity of packing rainbow spanning trees

DOI10.1016/J.DISC.2022.113297MaRDI QIDQ2685331zbMATH OpenOpenAlexFDO

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

Publication date 21 February 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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

Cites work

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

Cited in

(6)

• On the complexity of rainbow spanning forest problem
• Rainbow bases in matroids
• Diverse collections in matroids and graphs
• Problems on group-labeled matroid bases
• 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)