Bounded transversals in multipartite graphs |
| |
| Authors: | Robert Berke Penny Haxell Tibor Szabó |
| |
| Institution: | 1. Department of Mathematical and Computing Science, Tokyo Institute of Technology, , Meguro-Ku Okayama, Tokyo 152‐8552, Japan;2. Combinatorics 8 Optimization, University of Waterloo, , Ontario, Canada, N2L 3G1;3. Department of Mathematics and Computer Science, Free University Berlin, , 14195 Berlin, Germany |
| |
| Abstract: | 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. © 2011 Wiley Periodicals, Inc. J Graph Theory. |
| |
| Keywords: | transversals multipartite graphs |
|
|
