Extremal Problems For Transversals In Graphs With Bounded Degree |
| |
Authors: | Tibor Szabó Gábor Tardos? |
| |
Institution: | (1) Department of Computer Science, ETH, Zürich, 8092, Switzerland;(2) School of Computing Sciences, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada;(3) Alfréd Rényi Institute of Mathematics, 127, H-1364 Budapest, Hungary |
| |
Abstract: | We introduce and discuss generalizations of the problem of independent transversals. Given a graph property
, we investigate whether any graph of maximum degree at most d with a vertex partition into classes of size at least p admits a transversal having property
. In this paper we study this problem for the following properties
: “acyclic”, “H-free”, and “having connected components of order at most r”.
We strengthen a result of 13]. We prove that if the vertex set of a d-regular graph is partitioned into classes of size d+⌞d/r⌟, then it is possible to select a transversal inducing vertex disjoint trees on at most r vertices. Our approach applies appropriate triangulations of the simplex and Sperner’s Lemma. We also establish some limitations
on the power of this topological method.
We give constructions of vertex-partitioned graphs admitting no independent transversals that partially settles an old question
of Bollobás, Erdős and Szemerédi. An extension of this construction provides vertex-partitioned graphs with small degree such
that every transversal contains a fixed graph H as a subgraph.
Finally, we pose several open questions.
* Research supported by the joint Berlin/Zurichgrad uate program Combinatorics, Geometry, Computation, financed by the German
Science Foundation (DFG) and ETH Zürich.
† Research partially supported by Hungarian National Research Fund grants T-037846, T-046234 and AT-048826. |
| |
Keywords: | 05D15 05C15 05C69 |
本文献已被 SpringerLink 等数据库收录! |
|