Graphs of low average degree without independent transversals

• Published in: Journal of graph theory 2023-02, Vol.102 (2), p.374-387
• Main Authors: Groenland, Carla, Kaiser, Tomáš, Treffers, Oscar, Wales, Matthew
• Format: Article
• Language: English
• Subjects: Apexes; average degree; counterexample; hypergraph; independent transversal; maximum block average degree
• ISSN: 0364-9024; 1097-0118
• DOI: 10.1002/jgt.22876

An independent transversal of a graph G $G$ with a vertex partition P ${\mathscr{P}}$ is an independent set of G $G$ intersecting each block of P ${\mathscr{P}}$ in a single vertex. Wanless and Wood proved that if each block of P ${\mathscr{P}}$ has size at least t $t$ and the average degree of vertices in each block is at most t ∕ 4 $t\unicode{x02215}4$, then an independent transversal of P ${\mathscr{P}}$ exists. We present a construction showing that this result is optimal: for any ε > 0 $\varepsilon \gt 0$ and sufficiently large t $t$, there is a forest with a vertex partition into parts of size at least t $t$ such that the average degree of vertices in each block is at most (1 4 + ε ) t $(\frac{1}{4}+\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.