Back to Search
Start Over
A PRECISE CONDITION FOR INDEPENDENT TRANSVERSALS IN BIPARTITE COVERS.
- 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]
- Subjects :
- *BIPARTITE graphs
*TRANSVERSAL lines
*INDEPENDENT sets
*GRAPH coloring
Subjects
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