Tree Matchings

DOI10.1002/JGT.22528MaRDI QIDQ6280515arXivFDO

Authors Alexander Roberts

Publication date 6 December 2016

Published in arXiv

Full work available at URL https://doi.org/10.1002/JGT.22528

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

arXiv classification

math.CO

Abstract: An $(s,t)$-matching in a bipartite graph $G=(U,V,E)$ is a subset of the edges $F$ such that each component of $G[F]$ is a tree with at most $t$ edges and each vertex in $U$ has $s$ neighbours in $G[H]$. We give sharp conditions for a bipartite graph to contain an $(s,t)$-matching. As a special case, we prove a conjecture of Bonacina, Galesi, Huynh and Wollan cite{CNF}.

This page was built for publication: Tree Matchings

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