Abstract
A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaεA andbεB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log2(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
N. Alon, Choice numbers of graphs: a probabilistic approach, Combin. Probab. Comput.1 (1992) 107–114.
N. Alon, Restricted colorings of graphs, In: Surveys in Combinatorics 1993, London Math. Soc., Lecture Notes Series, Vol. 187, K. Walker, Ed., Cambridge University Press, 1993, pp. 1–33.
N. Alon, M. Krivelevich and B. Sudakov, List coloring of random and pseudo-random graphs, to appear.
P. Erdös, On a combinatorial problem II, Acta Math. Acad. Sci. Hungar.15 (1964) 445–447.
P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, In: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI, 1979, pp. 125–157.
V.G. Vizing, Coloring the vertices of a graph in prescribed colors, Diskret. Analiz. No. 29, Metody Diskret. Anal. v. Teorii Kodov i Shem101 (1976) 3–10 (in Russian).
Author information
Authors and Affiliations
Additional information
Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.
Research supported by an IAS/DIMACS Postdoctoral Fellowship.
Rights and permissions
About this article
Cite this article
Alon, N., Krivelevich, M. The choice number of random bipartite graphs. Annals of Combinatorics 2, 291–297 (1998). https://doi.org/10.1007/BF01608526
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01608526