Geometric graphs
Alexander Soifer · Cambridge University Press eBooks · 2015
In this chapter we address a colourful area of geometric graph theory: finding the chromatic number of the plane and related problems. In addition to results, we present open problems of a classical kind that are easy to understand, but hard to solve . The chromatic number of the plane In the definition of a graph, edges symbolize the adjacency of points and nothing else: we ignore their shape and length. However, the past century has witnessed a great deal of interest in geometric graphs , where geometrical considerations such as distance define the adjacency. The wealth of material related to geometric graphs is so vast that one can easily imagine a book written on this topic alone. In view of space and time limitations and our emphasis on chromatic graph theory, we have chosen to go deep and address a small but colourful area of geometric graphs: the problem of finding the chromatic number of the plane and related problems. My monograph [45] did not appear in that book. We can create a graph G from the Euclidean plane E 2 by taking all of its points as vertices, and joining two vertices by an edge if and only if they are at distance 1 apart. More generally, we call a graph unit-distance when any two vertices are adjacent if and only if they are at distance 1 apart. The main open problem in the subject is as follows. Problem Find the chromatic number of the above graph G . This number is called the chromatic number of the plane (CNP) and is denoted by χ ( E 2 ). As outlined in [45], this problem was created in late 1950 by the 18-year-old Edward Nelson, who determined a lower bound; his 20-year-old friend John Isbell found an upper bound: 4 ≤ χ ( E 2 ) ≤ 7 – that is, χ ( E 2 ) = 4, 5, 6 or 7.