Back to Search Start Over

A PRECISE CONDITION FOR INDEPENDENT TRANSVERSALS IN BIPARTITE COVERS.

Authors :
CAMBIE, STIJN
HAXELL, PENNY
KANG, ROSS J.
WDOWINSKI, RONEN
Source :
SIAM Journal on Discrete Mathematics. 2024, Vol. 38 Issue 2, p1451-1461. 11p.
Publication Year :
2024

Abstract

Given a bipartite graph H = (V = VA ∪ VB, E) in which any vertex in VA (resp., VB) has degree at most DA (resp., DB), suppose there is a partition of V that is a refinement of the bipartition VA ∪ VB such that the parts in VA (resp., VB) have size at least KA (resp., kB). We prove that the condition DA/kB + DB/kA ≤ 1 is sufficient for the existence of an independent set of vertices of H 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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
08954801
Volume :
38
Issue :
2
Database :
Academic Search Index
Journal :
SIAM Journal on Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
178602114
Full Text :
https://doi.org/10.1137/23M1600384