Skip to main content Accessibility help
×
Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T03:39:30.545Z Has data issue: false hasContentIssue false

8 - Geometric graphs

Published online by Cambridge University Press:  05 May 2015

Alexander Soifer
Affiliation:
University of Colorado
Lowell W. Beineke
Affiliation:
Purdue University, Indiana
Robin J. Wilson
Affiliation:
The Open University, Milton Keynes
HTML view is not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Summary

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 E2 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 χ(E2). 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 ≤ χ(E2) ≤ 7 – that is, χ(E2) = 4, 5, 6 or 7.

Information

Save book to Kindle

To save this book to your Kindle, first ensure no-reply@cambridge.org is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×