Đang chuẩn bị liên kết để tải về tài liệu:
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@kfupm.edu.sa 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 5.5 . THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R13 1 Apart from this very successful study of the .