TAILIEUCHUNG - Báo cáo toán học: "Sparse graphs usually have exponentially many optimal colorings"

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 .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
31    225    0    29-03-2024
44    181    0    29-03-2024
46    179    0    29-03-2024
8    163    0    29-03-2024
10    148    0    29-03-2024
22    112    0    29-03-2024
10    109    0    29-03-2024
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.