Graphs of low average degree without independent transversals

Carla Groenland*, Tomáš Kaiser, Oscar Treffers, Matthew Wales

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)

Abstract

An independent transversal of a graph (Formula presented.) with a vertex partition (Formula presented.) is an independent set of (Formula presented.) intersecting each block of (Formula presented.) in a single vertex. Wanless and Wood proved that if each block of (Formula presented.) has size at least (Formula presented.) and the average degree of vertices in each block is at most (Formula presented.), then an independent transversal of (Formula presented.) exists. We present a construction showing that this result is optimal: for any (Formula presented.) and sufficiently large (Formula presented.), there is a forest with a vertex partition into parts of size at least (Formula presented.) such that the average degree of vertices in each block is at most (Formula presented.), 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.

Original languageEnglish
Pages (from-to)374-387
Number of pages14
JournalJournal of Graph Theory
Volume102
Issue number2
DOIs
Publication statusPublished - 2023
Externally publishedYes

Keywords

  • average degree
  • counterexample
  • hypergraph
  • independent transversal
  • maximum block average degree

Fingerprint

Dive into the research topics of 'Graphs of low average degree without independent transversals'. Together they form a unique fingerprint.

Cite this