Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Unit distance graphs with ambiguous chromatic number. | Unit distance graphs with ambiguous chromatic number Michael S. Payne School of Mathematical Sciences Monash University and Institut fur Mathematik TU Berlin. michaelstuartpayne@gmail.com Submitted Aug 14 2009 Accepted Oct 30 2009 Published Nov 7 2009 Mathematics Subject Classification 05C15 Abstract First Laszlo Szekely and more recently Saharon Shelah and Alexander Soifer have presented examples of infinite graphs whose chromatic numbers depend on the axioms chosen for set theory. The existence of such graphs may be relevant to the Chromatic Number of the Plane problem. In this paper we construct a new class of graphs with ambiguous chromatic number. They are unit distance graphs with vertex set R and hence may be seen as further evidence that the chromatic number of the plane might depend on set theory. 1 Introduction The Chromatic Number of the Plane problem asks how many colours are required to colour the Euclidean plane if points that are distance 1 apart must receive different colours. The number is known to be between 4 and 7 inclusive. For a comprehensive history see 15 . We may view the problem as that of colouring an infinite graph lying in the plane. This graph which by abuse of notation we denote R2 has all points of the plane as its vertices and edges between points that are distance 1 apart. Any graph in the plane with straight unit length edges is therefore a subgraph of R2. In 1984 Laszlo Szekely investigated the difference between the usual chromatic number x and the measurable chromatic number xm for geometric graphs the latter being the chromatic number when only Lebesgue measurable colour sets are allowed 17 . He gave This work began as part of a Bachelor s thesis at Monash University and was extended while the author was studying with the support of the Berlin Mathematical School. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 N31 1 an example of a graph which could be 2-coloured in general but which needed 3 colours in the measurable case. .