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:List coloring hypergraphs. | List coloring hypergraphs Penny Haxell Jacques Verstraete Department of Combinatorics and Optimization Department of Mathematics University of Waterloo University of California Waterloo Ontario Canada San Diego CA pehaxell@ jverstra@ Submitted Apr 29 2010 Accepted Sep 6 2010 Published Sep 22 2010 Mathematics Subject Classification 05C15 05C65 Abstract Let H be a hypergraph and let Lv v E V H be sets we refer to these sets as lists and their elements as colors. A list coloring of H is an assignment of a color from Lv to each v E V H in such a way that every edge of H contains a pair of vertices of different colors. The hypergraph H is k-list-colorable if it has a list coloring from any collection of lists of size k. The list chromatic number of H is the minimum k such that H is k-list-colorable. In this paper we prove that every d-regular three-uniform linear hypergraph has list chromatic number at least logd l 2 nmvided d. is Inrơm in iii i li On I Im other hand there evisl y 5 log log d p r o men. Lu is large eno ugn. _z 11 L lie o Lil er rr arm Lil er e e xis L Lv 1 eg mar three-uniform linear hypergraphs with list chromatic number at most log3 d 3. This leaves the question open as to the existence of such hypergraphs with list chromatic number o log d as d TO. 1 Introduction A hypergraph H is k-uniform if every edge of H has size k and d-regular if every vertex of H is in exactly d edges of H. A hypergraph is linear if any pair of distinct edges of the hypergraph intersect in at most one vertex. Let H be a hypergraph and let Lv v E V H be sets we refer to these sets as lists. A list coloring of H is an assignment of an element of Lv to each v E V H in such a way that every edge of H contains a pair of vertices assigned different elements. The hypergraph H is called k-list-colorable if it has a list coloring from any collection of lists of size k. The list chromatic number Xi H of H also called the choice number of H is the .
