An independent transversal of a graph with a vertex partition $\mathcal PG\mathcal P$ in a single vertex. Wanless and Wood proved that if each block of has size at least and the average degree of vertices in each block is at most , then an independent transversal of exists. We present a construction showing that this result is optimal: for any and sufficiently large , there is a family of forests with vertex partitions whose block size is at least , average degree of vertices in each block is at most , 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.

生成讲解博客的中文版本

生成AI智能校验的中文版本