Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài:On a theorem of Erd˝s, Rubin, and Taylor on o choosability of complete bipartite graphs. | On a theorem of Erdos Rubin and Taylor on choosability of complete bipartite graphs Alexandr Kostochka University of Illinois at Urbana-Champaign Urbana IL 61801 and Institute of Mathematics Novosibirsk 630090 Russia kostochk@ Submitted April 10 2002 Accepted August 13 2002. MR Subject Classifications 05C15 05C65 Abstract Erdos Rubin and Taylor found a nice correspondence between the minimum order of a complete bipartite graph that is not r-choosable and the minimum number of edges in an r-uniform hypergraph that is not 2-colorable in the ordinary sense . In this note we use their ideas to derive similar correspondences for complete k-partite graphs and complete k-uniform k-partite hypergraphs. 1 Introduction Let m r k denote the minimum number of edges in an r-uniform hypergraph with chromatic number greater than k and N k r denote the minimum number of vertices in a k-partite graph with list chromatic number greater than r. Erdos Rubin and Taylor 6 p. 129 proved the following correspondence between m r 2 and N 2 r . Theorem 1 For every r 2 m r 2 N 2 r 2m r 2 . This nice result shows close relations between ordinary hypergraph 2-coloring and list coloring of complete bipartite graphs. Note that m r 2 was studied in 2 3 4 9 10 . Using known bounds on m r 2 Theorem 1 yields the corresponding bounds for N 2 r c 2 4-0 N 2 r C 2rr2. ln r This work was partially supported by the NSF grant DMS-0099608 and the Dutch-Russian Grant NW0-047-008-006. THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 N9 1 Theorem 1 can be extended in a natural way in two directions to complete fe-partite graphs and to fe-uniform fe-partite hypergraphs. In this note we present these extensions using the ideas of Erdos Rubin and Taylor . A vertex t-coloring of a hypergraph H is panchromatic if each of the t colors is used on every edge of G. Thus an ordinary 2-coloring is panchromatic. Some results on the existence of panchromatic colorings for hypergraphs with few edges can be found .