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: Sparse graphs usually have exponentially many optimal colorings. | Sparse graphs usually have exponentially many optimal colorings Michael Krivelevich Department of Mathematics Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv 69978 Israel. krivelev@ Submitted September 6 2001 Accepted June 8 2002 MR Subject Classification 05C80 05C15 Abstract A proper coloring of a graph G u E is called optimal if the number of colors used is the minimal possible . it coincides with the chromatic number of G. We investigate the typical behavior of the number of distinct optimal colorings of a random graph G n p for various values of the edge probability p p n . Our main result shows that for every constant 1 3 a 2 most of the graphs in the probability space G n p with p n-a have exponentially many optimal colorings. Given a graph G V E an unordered partition V V1 u . u Vk is called a k-coloring if each of the color classes V is an independent set of G. It is important to observe that we consider unordered partitions only and therefore two k-colorings V1 . Vk and U1 . Uk for which there exists a permutation Ơ 2 Sk satisfying Vi Uơ i 1 i k are considered to be indistinguishable. A k-coloring V1 . Vk of G is optimal if the number of colors is the minimal possible . k x G where x G denotes as usually the chromatic number of G. Here are two simple examples to illustrate the above definitions a the graph G Kn e has chromatic number x G n 1 and a unique optimal coloring b Define G V E as follows V A u B A n B 0 A 1 B n 2 fix two distinct vertices u v 2 B and define E G a b a 2 A b 2 Bg u u v g. Then it is easy to see that x G 3 and G has exactly 2n 2 optimal colorings where each optimal coloring has the following form Vi V2 V3 where V1 A u 2 V2 v 2 V3. How many optimal colorings does a typical graph G on n vertices with given density p E G yn have In order to address this question quantitatively we need to introduce a probability space of graphs on n vertices to make the notion of a typical graphs Supported by a .
