Full metadata record
DC FieldValueLanguage
dc.contributor.authorGroenland, Carla
dc.contributor.authorKaiser, Tomáš
dc.contributor.authorTreffers, Oscar
dc.contributor.authorWales, Matthew
dc.date.accessioned2023-01-30T11:00:33Z-
dc.date.available2023-01-30T11:00:33Z-
dc.date.issued2023
dc.identifier.citationGROENLAND, 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-9024cs
dc.identifier.issn0364-9024
dc.identifier.uri2-s2.0-85135964681
dc.identifier.urihttp://hdl.handle.net/11025/51215
dc.format14 s.cs
dc.format.mimetypeapplication/pdf
dc.language.isoenen
dc.publisherWileyen
dc.relation.ispartofseriesJournal of Graph Theoryen
dc.rights© authorsen
dc.titleGraphs of low average degree without independent transversalsen
dc.typečlánekcs
dc.typearticleen
dc.rights.accessopenAccessen
dc.type.versionpublishedVersionen
dc.description.abstract-translatedAn 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.en
dc.subject.translatedindependent transversalen
dc.subject.translatedLovász Local Lemmaen
dc.subject.translatedentropy compressionen
dc.identifier.doi10.1002/jgt.22876
dc.type.statusPeer-revieweden
dc.identifier.document-number841136400001
dc.identifier.obd43937771
dc.project.IDGA20-09525S/Strukturální vlastnosti tříd grafů charakterizovaných zakázanými indukovanými podgrafycs
Appears in Collections:Články / Articles (KMA)
OBD

Files in This Item:
File SizeFormat 
17480767.pdf690,56 kBAdobe PDFView/Open
Show simple item record


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.

search
navigation
  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD