Graphs of low average degree without independent transversals

An independent transversal of a graph $G$ with a vertex partition $\mathcal P$ is an independent set of $G$ intersecting each block of $\mathcal P$ in a single vertex. Wanless and Wood proved that if each block of $\mathcal P$ has size at least $t$ and the average degree of vertices in each block is at most $t/4$, then an independent transversal of $\mathcal P$ exists. We present a construction showing that this result is optimal: for any $\varepsilon > 0$ and sufficiently large $t$, there is a family of forests with vertex partitions whose block size is at least $t$, average degree of vertices in each block is at most $(\frac14+\varepsilon)t$, and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld-Wanless-Wood scheme or the Local Cut Lemma are tight for this problem. Further constructions are given for variants of the problem, including the hypergraph version.

No reviews yet.

No comments yet.