Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A Paintability Version of the Combinatorial Nullstellensatz, and List Colorings of k-partite k-uniform Hypergraphs"

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: A Paintability Version of the Combinatorial Nullstellensatz, and List Colorings of k-partite k-uniform Hypergraphs. | A Paintability Version of the Combinatorial Nullstellensatz and List Colorings of k-partite k-uniform Hypergraphs Uwe Schauz Department of Mathematics and Statistics King Fahd University of Petroleum and Minerals Dhahran 31261 Saudi Arabia schauz@kfupm.edu.sa Submitted May 15 2010 Accepted Dec 2 1010 Published Dec 10 2010 Mathematics Subject Classifications 05C15 11C08 91A43 05C65 05C50 Abstract We study the list coloring number of k-uniform k-partite hypergraphs. Answering a question of Ramamurthi and West we present a new upper bound which generalizes Alon and Tarsi s bound for bipartite graphs the case k 2. Our results hold even for paintability on-line list colorability . To prove this additional strengthening we provide a new subject-specific version of the Combinatorial Null-stellensatz. 1 Introduction We examine list colorability choosability of hypergraphs H V E . For a fixed tuple L Lv v y of color lists sets the hypergraph H is called L-colorable if there exist a vertex coloring v I c v G Lv without monochromatic edges e G E i.e. c e 1. For a fixed tuple t U v y G Z Q the hypergraph H is called Ế-list colorable h-choosable if it is L-colorable for any tuple L of color lists Lv with cardinalities Lv Ếv. As generalization of ordinary graph colorings with just one common list of available colors for all vertices list colorings were introduced by Vizing Viz and independently by Erdos Rubin and Taylor ERT . They worked with usual graphs i.e. 2-uniform hypergraphs e 2 for all e G E and proved that Brooks Theorem about the maximal degree as upper bound for the required number of colors holds in the more general setting of list colorings. Other theorems about usual colorings could be generalized later as well see Tu Al KTV . One could think that if we can color a graph with k colors then it should be k-list colorable i.e k k . k -list colorable making habitats less overlapping should THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R176 1 help to avoid collisions