Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Towards the Albertson conjecture"

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@dcs.vein.hu Geza Toth Renyi Institute Realtanoda u. 13-15 1052 Budapest Hungary geza@renyi.hu 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 .