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: Towards the Albertson conjecture. | Towards the Albertson conjecture János Barat Department of Computer Science and Systems Technology University of Pannonia Egyetem u. 10 8200 Veszprem Hungary barat@ Geza Toth Renyi Institute Realtanoda u. 13-15 1052 Budapest Hungary geza@ Submitted Sep 2 2009 Accepted May 7 2010 Published May 14 2010 Mathematics Subject Classification 05C10 05C15 Abstract Albertson conjectured that if a graph G has chromatic number r then the crossing number of G is at least as large as the crossing number of Kr the complete graph on r vertices. Albertson Cranston and Fox verified the conjecture for r 12. In this paper we prove it for r 16. Dedicated to the memory of Michael O. Albertson. 1 Introduction Graphs in this paper are without loops and multiple edges. Every planar graph is four-colorable by the Four Color Theorem 2 24 . The efforts to solve the Four Color Problem had a great effect on the development of graph theory and FCT is one of the most important theorems of the field. The crossing number of a graph G denoted CR G is the minimum number of edge crossings in a drawing of G in the plane. It is a natural relaxation of planarity see 25 for a survey. The chromatic number of a graph G denoted x G is the minimum number of colors in a proper coloring of G. The Four Color Theorem states if Cr G 0 then x G 4. Oporowski and Zhao 18 proved that every graph with crossing number at most two is 5-colorable. Albertson et al. 5 showed that if Cr G 6 then x G 6. It Research is supported by OTKA Grants PD 75837 and K 76099 and the Janos Bolyai Research Scholarship of the Hungarian Academy of Sciences. Research is supported by OTKA T 038397 and T 046246. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R73 1 was observed by Schaefer that if CR G k then x G O tfk and this is the correct order of magnitude 4 . Graphs with chromatic number r do not necessarily contain Kr as a subgraph they can have clique number 2 see 27 . The Hajos conjecture proposed that graphs with .
