TAILIEUCHUNG - Báo cáo toán học: "List coloring 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: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 .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học