A Precise Condition for Independent Transversals in Bipartite Covers

Authors:
Publisher website
Google Scholar
Abstract
Given a bipartite graph [Formula: see text] in which any vertex in [Formula: see text] (resp., [Formula: see text]) has degree at most [Formula: see text] (resp., [Formula: see text]), suppose there is a partition of [Formula: see text] that is a refinement of the bipartition [Formula: see text] such that the parts in [Formula: see text] (resp., [Formula: see text]) have size at least [Formula: see text] (resp., [Formula: see text]). We prove that the condition [Formula: see text] is sufficient for the existence of an independent set of vertices of [Formula: see text] that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos.
Funding Information
  • Natural Sciences and Engineering Research Council of Canada
  • Institute for Basic Science (IBS-R029-C4)
  • KU Leuven (PDMT1/22/005)
  • KU Leuven
  • Nederlandse Organisatie voor Wetenschappelijk Onderzoek (639.032.614, 024.002.003)

This publication has 13 references indexed in Scilit: