Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: On the chromatic number of intersection graphs of convex sets in the plane. | On the chromatic number of intersection graphs of convex sets in the plane Seog-Jin Kim Department of Mathematics University of Illinois Urbana IL 61801 USA skim12@ Alexandr Kostochka Department of Mathematics University of Illinois Urbana IL 61801 USA and Institute of Mathematics 630090 Novosibirsk Russia kostochk@ Kittikorn Nakprasit Department of Mathematics University of Illinois Urbana IL 61801 USA nakprasi@ Submitted Dec 10 2002 Accepted May 21 2004 Published Aug 19 2004 MR Subject Classifications 05C15 05C35 Abstract Let G be the intersection graph of a finite family of convex sets obtained by translations of a fixed convex set in the plane. We show that every such graph with clique number k is 3k 3 -degenerate. This bound is sharp. As a consequence we derive that G is 3k 2 -colorable. We show also that the chromatic number of every intersection graph H of a family of homothetic copies of a fixed convex set in the plane with clique number k is at most 6k 6. 1 Introduction The intersection graph G of a family F of sets is the graph with vertex set F where two members of F are adjacent if and only if they have common elements. Asplund and Grunbaum 3 and Gyarfas and Lehel 11 9 started studying many interesting problems This work was partially supported by the NSF grants DMS-0099608 and DMS-00400498. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R52 1 on the chromatic number of intersection graphs of convex figures in the plane. Many problems of this type can be stated as follows. For a class Q of intersection graphs and for a positive integer k find or bound f Q k - the maximum chromatic number of a graph in Q with the clique number at most k. A number of results on the topic can be found in 5 9 11 13 . Recently several papers on intersection graphs of translations of a plane figure appeared. Akiyama Hosono and Urabe 2 considered f C k where C is the family of intersection graphs of unit squares on the plane with sides .
