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) 107114.

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. 133.

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) 445447.

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. 125157.

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) 310 (in Russian).

Get the DVI| PS| PDF file of this abstract.