A precise condition for independent transversals in bipartite covers

EUROCOMB’23

Abstract
Given a bipartite graph $H=(V=V_A\cup V_B,E)$ in which any vertex in $V_A$ (resp. $V_B$) has degree at most $D_A$ (resp. $D_B$), suppose there is a partition of $V$ that is a refinement of the bipartition $V_A\cup V_B$ such that the parts in $V_A$ (resp. $V_B$) have size at least $k_A$ (resp. $k_B$). We prove that the condition $D_A/k_A+D_B/k_B\le 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.

Pages:
263–269
References

N. Alon, S. Cambie, and R. J. Kang. Asymmetric list sizes in bipartite graphs. Ann. Comb., 25(4):913-933, 2021.
https://doi.org/10.1007/s00026-021-00552-5

N. Alon and M. Krivelevich. The choice number of random bipartite graphs. Ann. Comb., 2(4):291-297, 1998.
https://doi.org/10.1007/BF01608526

B. Bollobás, P. Erdős, and E. Szemerédi. On complete subgraphs of r-chromatic graphs. Discrete Math., 13(2):97-107, 1975.
https://doi.org/10.1016/0012-365X(75)90011-4

S. Cambie and R. J. Kang. Independent transversals in bipartite correspondence-covers. Canad. Math. Bull., 65(4):882-894, 2022.
https://doi.org/10.4153/S0008439521001004

P. Erdős, A. L. Rubin, and H. Taylor. Choosability in graphs. In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, pages 125-157, Winnipeg, Man., 1980. Utilitas Math.

P. Haxell. On forming committees. Amer. Math. Monthly, 118(9):777-788, 2011.
https://doi.org/10.4169/amer.math.monthly.118.09.777

P. E. Haxell. A note on vertex list colouring. Combin. Probab. Comput., 10(4):345-347, 2001.
https://doi.org/10.1017/S0963548301004758

A. Johansson. Asymptotic choice number for triangle-free graphs. Technical Report 91-5, DIMACS, 1996.

D. Král, O. Pangrác, and H.-J. Voss. A note on group colorings. J. Graph Theory, 50(2):123-129, 2005.
https://doi.org/10.1002/jgt.20098

B. Reed. The list colouring constants. J. Graph Theory, 31(2):149-153, 1999.
https://doi.org/10.1002/(SICI)1097-0118(199906)31:2<149::AID-JGT8>3.0.CO;2-#

T. Szabó and G. Tardos. Extremal problems for transversals in graphs with bounded degree. Combinatorica, 26(3):333-351, 2006.
https://doi.org/10.1007/s00493-006-0019-9

V. G. Vizing. Coloring the vertices of a graph in prescribed colors. Diskret. Analiz, 29 Metody Diskret. Anal. v Teorii Kodov i Shem:3-10, 101, 1976.

Metrics

0

Views

0

PDF views