Graphs of low average degree without independent transversals

DOI10.1002/JGT.22876MaRDI QIDQ6093156zbMATH OpenOpenAlexFDO

Authors Carla Groenland, Tomáš Kaiser, Matthew Wales

Publication date 6 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2106.15175

zbMATH Keywords

average degreecounterexamplehypergraphindependent transversalmaximum block average degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Abstract: An independent transversal of a graph $G$ with a vertex partition $mathcalP$ is an independent set of $G$ intersecting each block of $mathcalP$ in a single vertex. Wanless and Wood proved that if each block of $mathcalP$ has size at least $t$ and the average degree of vertices in each block is at most $t/4$, then an independent transversal of $mathcalP$ exists. We present a construction showing that this result is optimal: for any $varepsilon>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 $(frac14+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.

Recommendations

• An average degree condition for independent transversals
• Independent transversals in locally sparse graphs
• Colorings, transversals, and local sparsity
• Extremal problems for transversals in graphs with bounded degree
• Finding independent transversals efficiently

Cites work

• A note on vertex list colouring
• An average degree condition for independent transversals
• An improved bound for the strong chromatic number
• Another approach to non-repetitive colorings of graphs of bounded degree
• Colorings, transversals, and local sparsity
• Complete Subgraphs of r-partite Graphs
• Domination numbers and homology
• Extremal problems for transversals in graphs with bounded degree
• Hall's theorem for hypergraphs
• Independent systems of representatives in weighted graphs
• Independent transversals in \(r\)-partite graphs
• Independent transversals in locally sparse graphs
• Odd Independent Transversals are Odd
• On complete subgraphs of r-chromatic graphs
• Polynomial treewidth forces a large grid-like-minor
• Probabilistic methods in coloring and decomposition problems
• Problems and results in extremal combinatorics. I.
• Single‐conflict colouring
• The clique complex and hypergraph matching
• The intersection of a matroid and a simplicial complex
• The linear arboricity of graphs
• The local cut lemma
• Transversals of Vertex Partitions in Graphs

Cited in

(8)

• An average degree condition for independent transversals
• Finding independent transversals efficiently
• Colorings, transversals, and local sparsity
• Degree criteria and stability for independent transversals
• Constructing graphs with no independent transversals
• Single-conflict colorings of degenerate graphs
• Single-conflict colorings of degenerate graphs (extended abstract)
• Extremal problems for transversals in graphs with bounded degree

This page was built for publication: Graphs of low average degree without independent transversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093156)