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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài:Coloring the edges of a random graph without a monochromatic giant component. | Coloring the edges of a random graph without a monochromatic giant component Reto Spohel Angelika Steger Institute of Theoretical Computer Science Institute of Theoretical Computer Science ETH Zurich Switzerland ETH Zurich Switzerland rspoehel@ asteger@ Henning Thomas Institute of Theoretical Computer Science ETH Zuurich Switzerland hthomas@ Submitted Mar 25 2010 Accepted Sep 19 2010 Published Oct 5 2010 Mathematics Subject Classification 05C80 05C15 Abstract We study the following two problems i Given a random graph Gn m a graph drawn uniformly at random from all graphs on n vertices with exactly m edges can we color its edges with r colors such that no color class contains a component of size O n ii Given a random graph Gn m with a random partition of its edge set into sets of size r can we color its edges with r colors subject to the restriction that every color is used for exactly one edge in every set of the partition such that no color class contains a component of size O n We prove that for any fixed r 2 in both settings the sharp threshold for the existence of such a coloring coincides with the known threshold for r-orientability of Gnm which is at m rc n for some analytically computable constant c . The fact that the two problems have the same threshold is in contrast with known results for the two corresponding Achlioptas-type problems. 1 Introduction One of the most prominent areas of research in random graph theory is the component structure of the random graph Gn m a graph drawn uniformly at random from all graphs A preliminary version of this paper appeared in the proceedings of the European Conference on Combinatorics Graph Theory and Applications EuroComb 2009 17 . iThe author was supported by the Swiss National Science Foundation grant 200020-119918. He is now at MPI Saarbrucken. The author was supported by the Swiss National Science Foundation grant 200021-120284. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 .
