Transversals in r ‐partite graphs with various properties are known to have many applications in graph theory and theoretical computer science. We investigate f ‐ bounded transversal s (or f ‐ BT ), that is, transversals whose connected components have order at most f . In some sense we search for the sparsest f ‐BT‐free graphs. We obtain estimates on the smallest maximum degree that 3‐partite and 4‐partite graphs without 2‐BT can have and provide a greatly simplified proof of the best known general lower bound on the smallest maximum degree in f ‐BT‐free graphs.
No takes yet. Share an insight, caveat, or question.
Berke et al. (2011) studied this question.
Synapse has enriched 4 closely related papers on similar clinical questions. Consider them for comparative context: