Graphs of low average degree without independent transversals. (English) Zbl 1522.05491
Summary: An independent transversal of a graph \(G\) with a vertex partition \(\mathcal{P}\) is an independent set of \(G\) intersecting each block of \(\mathcal{P}\) in a single vertex. I. M. Wanless and D. R. Wood [“Exponentially many hypergraph colourings”, Preprint, arXiv:2008.00775] proved that if each block of \(\mathcal{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 \(\mathcal{P}\) exists. We present a construction showing that this result is optimal: for any \(\varepsilon >0\) and sufficiently large \(t\), there is a forest with a vertex partition into parts of size at least \(t\) such that the average degree of vertices in each block is at most \((\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.
{© 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.}
{© 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.}
MSC:
| 05D15 | Transversal (matching) theory |
| 05C07 | Vertex degrees |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Keywords:
average degree; counterexample; hypergraph; independent transversal; maximum block average degreeReferences:
| [1] | R.Aharoni and E.Berger, The intersection of a matroid and a simplicial complex, Trans. Am. Math. Society. 358 (2006), 4895-4917. · Zbl 1108.05023 |
| [2] | R.Aharoni, E.Berger, and R.Ziv, Independent systems of representatives in weighted graphs, Combinatorica. 27 (2007), no. 3, 253-267. · Zbl 1164.05020 |
| [3] | R.Aharoni and P. E.Haxell, Hall’s theorem for hypergraphs, J. Graph Theory. 35 (2000), no. 2, 83-88. · Zbl 0956.05075 |
| [4] | N.Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988), no. 3, 311-325. · Zbl 0673.05019 |
| [5] | N.Alon, Probabilistic methods in coloring and decomposition problems, Discrete Math.127 (1994), no. 1, 31-46. · Zbl 0804.05033 |
| [6] | N.Alon, Problems and results in extremal combinatorics, part I, Discrete Math.273 (2003), 31-53. · Zbl 1033.05060 |
| [7] | N.Alon and J. H.Spencer, The Probabilistic Method, 4th ed., Wiley‐Interscience, 2015. |
| [8] | B.Bollobás, P.Erdős, and E.Szemerédi, On complete subgraphs of \(r\)‐chromatic graphs, Discrete Math.13 (1975), no. 2, 97-107. · Zbl 0306.05121 |
| [9] | A. F.Beardon, The Geometry of Discrete Groups, vol. 91, Graduate Texts in Mathematics, 2nd ed., Springer‐Verlag, New York, 1995. |
| [10] | A.Bernshteyn, The local cut lemma, Eur. J. Comb. 63 (2017), 95-114. · Zbl 1365.05288 |
| [11] | Z.Dvořák, L.Esperet, R. J.Kang, and K.Ozeki, Single‐conflict colouring, J. Graph Theory. 97 (2021), no. 1, 148-160. · Zbl 1521.05041 |
| [12] | P.Erdős, Problem 2, Combinatorics (D. J. A.Fellows (ed.) and D. R.Woodall (ed.), eds.), The Institute of Mathematics and its Applications, 1972, pp. 353-354. |
| [13] | M. R.Fellows, Transversals of vertex partitions in graphs, SIAM J. Discrete Math. 3 (1990), no. 2, 206-215. · Zbl 0735.05057 |
| [14] | S.Glock and B.Sudakov, An average degree condition for independent transversals, J. Comb. Theory Ser. B. 154 (2022), 370-391. https://doi.org/10.1016/j.jctb.2022.01.004 · Zbl 1483.05197 · doi:10.1016/j.jctb.2022.01.004 |
| [15] | P. E.Haxell, A note on vertex list colouring, Comb. Prob. Comput. 10 (2001), no. 4, 345-347. · Zbl 0986.05042 |
| [16] | P. E.Haxell, An improved bound for the strong chromatic number, J. Graph Theory. 58 (2008), no. 2, 148-158. · Zbl 1149.05017 |
| [17] | P. E.Haxell and T.Szabó, Odd independent transversals are odd, Comb. Prob. Comput. 15 (2006), no. 1-2, 193-211. · Zbl 1082.05068 |
| [18] | G.Jin, Complete subgraphs of \(r\)‐partite graphs, Comb. Prob. Comput. 1 (1992), no. 3, 241-250. · Zbl 0793.05088 |
| [19] | R. J.Kang and T.Kelly, Colourings, transversals and local sparsity, Random Struct. Algorithms. 61 (2021), 173-192. · Zbl 1522.05493 |
| [20] | P.‐S.Loh and B.Sudakov, Independent transversals in locally sparse graphs, J. Comb. Theory Series B. 97 (2007), no. 6, 904-918. · Zbl 1125.05040 |
| [21] | R.Meshulam, The clique complex and hypergraph matching, Combinatorica. 21 (2001), no. 1, 89-94. · Zbl 1107.05302 |
| [22] | R.Meshulam, Domination numbers and homology, J. Comb. Theory A. 102 (2003), no. 2, 321-330. · Zbl 1030.05086 |
| [23] | B. A.Reed and D. R.Wood, Polynomial treewidth forces a large grid‐like‐minor, Eur. J. Comb. 33 (2012), no. 3, 374-379. · Zbl 1234.05223 |
| [24] | M.Rosenfeld, Another approach to non‐repetitive colorings of graphs of bounded degree, Electron J. Comb. 27 (2020), no. 3, P3.43. · Zbl 1441.05083 |
| [25] | T.Szabó and G.Tardos, Extremal problems for transversals in graphs with bounded degree, Combinatorica. 26 (2006), no. 3, 333-351. · Zbl 1106.05100 |
| [26] | I. M.Wanless and D. R.Wood, Exponentially many hypergraph colourings, arXiv:2008.00775 [math.CO]. 2020. |
| [27] | R.Yuster, Independent transversals in \(r\)‐partite graphs, Disc. Math.176 (1997), no. 1, 255-261. · Zbl 0891.05041 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
