# Báo cáo toán học: "Flexible Color Lists in Alon and Tarsi’s Theorem, and Time Scheduling with Unreliable Participants"

## 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: Flexible Color Lists in Alon and Tarsi’s Theorem, and Time Scheduling with Unreliable Participants. | Flexible Color Lists in Alon and Tarsi s Theorem and Time Scheduling with Unreliable Participants Uwe Schauz Department of Mathematics and Statistics King Fahd University of Petroleum and Minerals Dhahran 31261 Saudi Arabia schauz@ Submitted Jul 21 2008 Accepted Dec 11 2009 Published Jan 5 2010 Mathematics Subject Classifications 91A43 05C15 05C20 05C45 Abstract We present a purely combinatorial proof of Alon and Tarsi s Theorem about list colorings and orientations of graphs. More precisely we describe a winning strategy for Mrs. Correct in the corresponding coloring game of Mr. Paint and Mrs. Correct. This strategy produces correct vertex colorings even if the colors are taken from lists that are not completely fixed before the coloration process starts. The resulting strengthening of Alon and Tarsi s Theorem leads also to strengthening of its numerous repercussions. For example we study upper bounds for list chromatic numbers of bipartite graphs and list chromatic indices of complete graphs. As real life application we examine a chess tournament time scheduling problem with unreliable participants. Introduction Alon and Tarsi s Theorem AlTa from 1992 about list colorings and orientations of graphs has many applications in the theory of graph colorings. We will resume and extend most of them in this article. However Alon and Tarsi s Theorem not only has many applications it also opened a door to a new very successful algebraic method. This so called Polynomial Method was explicitly worked out in Alon s paper Al2 where Alon suggested the name Combinatorial Nullstellensatz for the main algebraic tool behind it. We strengthened this Nullstellensatz in Scha2 with a quantitative formula and presented some easy-to-apply corollaries and new applications. Our formula led in particular to a quantitative version of Alon and Tarsi s Theorem Scha2 Corollary . THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R13 1 Apart from this very successful study of the .

TÀI LIỆU LIÊN QUAN
32    57    0
45    42    0
6    65    0
4    53    0
6    55    0
6    52    0
6    45    0
5    59    0
7    58    0
6    64    0
TÀI LIỆU XEM NHIỀU
13    32413    1640
3    19331    204
25    18613    3682
20    16735    1476
16    15728    2475
14    14304    2540
37    13028    2802
1    11304    401
3    10945    211
23    10534    384
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
76    49    3    30-06-2022
5    20    3    30-06-2022
16    74    2    30-06-2022
93    6    1    30-06-2022
12    15    2    30-06-2022
39    17    1    30-06-2022
12    9    1    30-06-2022
39    81    1    30-06-2022
19    29    2    30-06-2022
10    20    3    30-06-2022
4    19    2    30-06-2022
74    12    1    30-06-2022
65    14    1    30-06-2022
21    7    1    30-06-2022
40    7    1    30-06-2022
14    15    1    30-06-2022
88    19    1    30-06-2022
11    42    3    30-06-2022
4    9    1    30-06-2022
46    13    1    30-06-2022
TÀI LIỆU HOT
3    19331    204
13    32413    1640
3    1485    75
580    3625    343
584    1955    80
62    4366    1
171    3978    620
2    1735    72
51    2466    150
53    3329    175
Đã 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.