Independent transversals in locally sparse graphs

DOI10.1016/J.JCTB.2007.02.003MaRDI QIDQ2384801zbMATH OpenOpenAlexFDO

Authors Po-Shen Loh, Benny Sudakov

Publication date 10 October 2007

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

cooperative coloring independent transversals list coloring sparse graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Transversal (matching) theory (05D15) Combinatorial probability (60C05)

Abstract: Let G be a graph with maximum degree Delta whose vertex set is partitioned into parts V(G) = V_1 cup ... cup V_r. A transversal is a subset of V(G) containing exactly one vertex from each part V_i. If it is also an independent set, then we call it an independent transversal. The local degree of G is the maximum number of neighbors of a vertex v in a part V_i, taken over all choices of V_i and v ot in V_i. We prove that for every fixed epsilon > 0, if all part sizes |V_i| >= (1+epsilon)Delta and the local degree of G is o(Delta), then G has an independent transversal for sufficiently large Delta. This extends several previous results and settles (in a stronger form) a conjecture of Aharoni and Holzman. We then generalize this result to transversals that induce no cliques of size s. (Note that independent transversals correspond to s=2.) In that context, we prove that parts of size |V_i| >= (1+epsilon)[Delta/(s-1)] and local degree o(Delta) guarantee the existence of such a transversal, and we provide a construction that shows this is asymptotically tight.

Review text

Let \(G\) be a graph whose maximum degree is \(\Delta\). Assume that the vertex set \(V(G)\) has been partitioned into \(r\) disjoint parts: \(V=V_{1}\cup V_{2}\cup \cdots \cup V_{r}\). A transversal is a subset of \(V(G)\) containing exactly one vertex from each part \(V_{i}\). A transversal which is also an independent set in \(G\) is called an independent transversal. The aim of this paper is to give a sufficient condition for the graph to have an independent transversal. The precise statement is as follows: For every \(\varepsilon>0\), there is a \(\gamma>0\) such that, if \(G\) is a graph with maximum degree \(\leq \Delta\), all part sizes \(| V_{i}|\geq (1+\varepsilon)\Delta\), then provided the so-called local degree of the graph is \(\leq \gamma \Delta\), then there is an independent transversal for sufficiently large \(\Delta\). The definition of local degree is the maximum, over all parts \(V_{i}\) and all vertices \(v\notin V_{i}\), of the number of neighbours of \(v\) in \(V_{i}\). Note that a disjoint union of \(\Delta\) cliques of order \(\Delta+1\), the parts being constructed to have exactly one vertex of each clique in them, shows that one cannot improve the constant 1 in the lower bound on the size of the \(V_{i}\). This result generalises earlier work of a number of authors, and possible links with list colourings of graphs amongst other topics noted in the paper. The proof of the theorem proceeds by first reducing to the case where the local degree is bounded by a constant (rather than just being \(o(\Delta)\)). More precisely, it is shown that for a multipartite graph with maximum degree \(\leq \Delta\) and parts \(V_{1},\ldots V_{r}\) of size \(| V_{i}| \geq (1+\varepsilon)\Delta\) and local degree \(\leq \gamma \Delta\), there are subsets \(W_{i}\) of \(V_{i}\) such that \(G'\), the subgraph induced by \(\bigcup_{i}W_{i}\) has maximum degree \(\Delta'\leq (1+\varepsilon/3)\Delta^{1/3}\), each \(W_{i}\) has size at least \((1+\varepsilon/4)\Delta'\) and the local degree in \(G'\) is at most 10. The case when \(\Delta^{2/3}\leq 1/\gamma\) is a fairly straightforward application of the local lemma and concentration bounds, but the general case depends on a sequence of halving steps with some resultant technical complications. The main result is now proved by use of the ``semi-random method, which will construct the independent transversal in several iterations. Roughly, the idea is: For each iteration, activate each remaining part with probability \(1/\log(\Delta)\), select a vertex uniformly at random from each activated part, let \(T\) be the set of selected vertices. For each \(i\) and \(v\in V_{i}\cap T\), if \(v\) is not adjacent to any \(w\in V_{j}\cap T\) with \(j<i\), add \(v\) to the independent transversal: for each \(v\) added in the last step, delete the entire part containing it from \(G\), and delete all neighbours of vertices in \(T\) from \(G\). The aim is not to show that after performing several iterations, the remaining graph will have maximum degree \(\leq \Delta '\) and parts of size \(\geq 2e\Delta '\) for some \(\Delta '\). We then abort the algorithm and finish the proof using a result of N. Alon (which was one of the forerunners of the result in this paper). The key points are that parts remain large enough during this process, and that degrees decrease rapidly enough. This in turn depends on some non-trivial use of concentration inequalities (Chernoff, Talagrand, etc.). An independent transversal is a transversal which contains no \(K_{2}\) and so a natural generalisation is to ask for conditions that guarantee the existence of a \(K_{s}\)-free transversal in a graph \(G\) with maximum degree \(\Delta\). The authors prove the following generalisation of the main theorem. For every \(\varepsilon>0\) and integer \(s\geq 2\) there exists \(\gamma>0\) such that, if \(G\) is a graph of maximum degree at most \(\Delta\) whose vertex set is partitioned into parts \(V(G)=V_{1}\cup V_{2}\cup \cdots V_{r}\) of size \(| V_{i}| \geq (1+\varepsilon)\Delta/(s-1)\) and the local degree of \(G\) is at most \(\gamma \Delta\), then \(G\) has a \(K_{s}\)-free transversal. This result is asymptotically tight, as is shown by a graph with vertex set \(\{1,2,\dots \Delta+1\}\times \{1,2,\dots n\}\) with parts \(V_{i}=\{(i,j): 1\leq j\leq n\}\) and \((i,j)\) and \((k,\ell)\) are adjacent for all \(1\leq i\), \(k\leq \Delta+1\).

Recommendations

Cites work

Cited in

(35)

This page was built for publication: Independent transversals in locally sparse graphs

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