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\).