Annals of Combinatorics 2(1998) 291-297
The Choice Number of Randon Bipartite Graphs
Noga Alon and Michael Krivelevich
Department of Mathematics, Raymomd and Beverly Sackler Faculty of Exact Sciences, Tel Aviv Uiversity, Tel Aviv, Israel and Institute for Advanced Study, Princeton, NJ 08540, USA
School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA
Received September 17, 1998
AMS Subject Classification: 05C15, 05C35
Abstract. A random bipartite graph G(n,n,p)is obtained by taking two disjoint subsets of vertices A and B of cardinality n each, and by connecting each pair of vertices a A and b B by an edge randomly and independently with probality p=p(n). We show that the choice number of G(n,n,p)is, almost surely, (1+o(1))log2(np) for all values of the edge probability p=p(n), where the o(1) tends to 0 as np tends to infinity.
Keywords: choice number, random graphs, graph coloring
1. N. Alon, Choice numbers of graphs: a probabilistic approach, Combin. Probab. Comput. 1 (1992) 107–114.
2. 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.
3. N. Alon, M. Krivelevich and B. Sudakov, List coloring of random and pseudo-random graphs, to appear.
4. P. Erdös, On a combinatorial problem II, Acta Math. Acad. Sci. Hungar. 15 (1964) 445–447.
5. 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.
6. V.G. Vizing, Coloring the vertices of a graph in prescribed colors, Diskret. Analiz. No. 29, Metody Diskret. Anal. v. Teorii Kodov i Shem 101 (1976) 3–10 (in Russian).