Title: | Graphs of low average degree without independent transversals |
Authors: | Groenland, Carla Kaiser, Tomáš Treffers, Oscar Wales, Matthew |
Citation: | GROENLAND, C. KAISER, T. TREFFERS, O. WALES, M. Graphs of low average degree without independent transversals. Journal of Graph Theory, 2023, roč. 102, č. 2, s. 374-387. ISSN: 0364-9024 |
Issue Date: | 2023 |
Publisher: | Wiley |
Document type: | článek article |
URI: | 2-s2.0-85135964681 http://hdl.handle.net/11025/51215 |
ISSN: | 0364-9024 |
Keywords in different language: | independent transversal;Lovász Local Lemma;entropy compression |
Abstract in different language: | An independent transversal of a graph G with a vertex partition P is an independent set of G intersecting each block of P in a single vertex. Wanless and Wood proved that if each block of 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 P exists. We present a construction showing that this result is optimal: for any ε>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 (1/4+ε)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. |
Rights: | © authors |
Appears in Collections: | Články / Articles (KMA) OBD |
Files in This Item:
File | Size | Format | |
---|---|---|---|
17480767.pdf | 690,56 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/51215
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.