Graphs of low average degree without independent transversals

Abstract

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 $\epsilon >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 $(\frac{1}{4}+\epsilon )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.

12 pages, 2 figures