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: The Gr¨tzsch Theorem for the hypergraph of o maximal cliques. | The Grotzsch Theorem for the hypergraph of maximal cliques Bojan Mohar and Riste Skrekovski Department of Mathematics University of Ljubljana Jadranska 19 1111 Ljubljana Slovenia Submitted September 5 1998 Accepted June 7 1999. Mathematical Subject Classification 05C15 05C65. Abstract In this paper we extend the Grotzsch Theorem by proving that the clique hypergraph H G of every planar graph is 3-colorable. We also extend this result to list colorings by proving that H G is 4-choosable for every planar or projective planar graph G. Finally 4-choosability of H G is established for the class of locally planar graphs on arbitrary surfaces. 1 Introduction Let G be a graph. The hypergraph H H G with the same vertex set as G whose hyper edges are the maximal cliques of G is called the clique hypergraph of G. A k-coloring of H is a function c V H 1 . kg such that no edge of H is monochromatic . c e 2 for every e 2 E H . The Supported in part by the Ministry of Science and Technology of Slovenia Research Project J1-0502-0101-98. 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R26 2 minimal k such that H admits a k-coloring is called the chromatic number of H and is denoted by y H . The reader can hnd more about this kind of colorings in 2 5 . A k-list-assignment of G is a function L which assigns to each vertex v 2 V G a set L v called the list of v which has at least k elements. The elements of L v are called the admissible colors for v. An L-coloring of G or H G is a function c V G uvL v such that c v 2 L v for every v 2 V G and no edge of G or H G is monochromatic. A coloring of H G is strong if no 3-cycle of G is monochromatic. G or H G is strongly k-choosable if for every k-list-assignment L there exists a strong L-coloring of G or H G . If G is a triangle-free graph then H G G. Hence x H G y G . Grotzsch 4 see also 5 8 9 proved the following beautiful theorem. Theorem Grotzsch Every triangle-free planar .
