An Asymptotically Sharp Bound on the Maximum Number of Independent Transversals

Let G be a multipartite graph with partition V1, V2, …, Vk of V (G). Let di,j denote the edge density of the pair (Vi, Vj). An independent transversal is an independent set of G with exactly one vertex in each Vi . In this paper, we prove an asymptotically sharp upper bound on the maximum number of independent transversals given the di,j ’s.

Duke Scholars

Author Fan Wei Mathematics