Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-01-13T18:42:12.617Z Has data issue: false hasContentIssue false

8 - Geometric graphs

Published online by Cambridge University Press:  05 May 2015

By
Alexander Soifer
Edited by
Lowell W. Beineke  and
Robin J. Wilson
Alexander Soifer
Affiliation:
University of Colorado
Lowell W. Beineke
Affiliation:
Purdue University, Indiana
Robin J. Wilson
Affiliation:
The Open University, Milton Keynes
Get access

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.

Type
Chapter
Information
Topics in Chromatic Graph Theory , pp. 161 - 180
Publisher: Cambridge University Press
Print publication year: 2015

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. H., Ardal, J., Manuch, M., Rosenfeld, S., Shelah and L., Stacho, The odd-distance plane graph, Discrete Comput. Geom. 42 (2009), 132–141.Google Scholar
2. M., Benda and M., Perles, Colorings of metric spaces, Geombinatorics IX (3) (2000), 113–126.Google Scholar
3. N., Brown, N., Dunfield and G., Perry, Colorings of the plane I, Geombinatorics III (2) (1993), 24–31.Google Scholar
4. N., Brown, N., Dunfield and G., Perry, Colorings of the plane II, Geombinatorics III (3) (1993), 64–74.Google Scholar
5. N., Brown, N., Dunfield and G., Perry, Colorings of the plane III, Geombinatorics III (4) (1993), 110–114.Google Scholar
6. K., Cantwell, All regular polytopes are Ramsey, J. Combin. Theory (A) 114 (2007), 555–562.Google Scholar
7. J., Cibulka, On the chromatic number of real and rational spaces, Geombinatorics XVIII (2) (2008), 53–65.Google Scholar
8. J. H., Conway and N. J. A., Sloane, Sphere Packings, Lattices and Groups, 3rd edn., Springer-Verlag, 1999.Google Scholar
9. D., Coulson, A 15-colouring of 3-space omitting distance one, Discrete Math. 256 (2002), 83–90.Google Scholar
10. D., Coulson, Tilings and colourings of 3-space, Geombinatorics XII (3) (2003), 102–116.Google Scholar
11. N. G., de Bruijn and P., Erdős, A color problem for infinite graphs and a problem in the theory of relations, Indag. Math. 13 (1951), 369–373.Google Scholar
12. P., Erdős, Problem (p. 681); Unsolved problems, Proceedings of the Fifth British Combinatorial Conference 1975, University of Aberdeen, July 1975 (eds. C. St.J. A., Nash-Williams and J., Sheehan), Congr. Numer. XV, Utilitas Mathematica, 1976.
13. P., Erdős, Combinatorial problems in geometry and number theory, Relations between combinatorics and other parts of mathematics, Proc. Sympos. Pure Math. (Ohio State Univ., 1978), Proc. Sympos. Pure Math. XXXIV, Amer. Math. Soc. (1979), 149–162.Google Scholar
14. P., Erdős, Some combinatorial problems in geometry, Geom. & Diff. Geom. (Proc. Haifa, 1979), Lecture Notes in Math. 792, Springer (1980), 46–53.Google Scholar
15. P., Erdős, Some new problems and results in graph theory and other branches of combinatorial mathematics, Combinatorics and Graph Theory (Proc. Symp. Calcutta 1980), Lecture Notes in Math. 885, Springer (1981), 9–17.Google Scholar
16. K. J., Falconer, The realization of distances in measurable subsets covering Rn, J. Combin. Theory (A) 31 (1981), 187–189.Google Scholar
17. K. J., Falconer, and J. M., Marstrand, Plane sets with positive density at infinity contain all large distances, Bull. London Math. Soc. 18 (1986), 471–474.Google Scholar
18. P., Frankl and R. M., Wilson, Intersection theorems with geometrical consequences, Combinatorica 1 (1981), 357–368.Google Scholar
19. R. L., Graham, Some of my favourite problems in Ramsey theory, Proceedings of the ‘Integers Conference 2005’ in Celebration of the 70th Birthday of Ronald Graham, Carrolton, Georgia, USA, 2005 (eds. B., Landman et al.), Walter de Gruyter (2007), 229–236.Google Scholar
20. R. L., Graham, Old and new problems and results in Ramsey theory, Horizons of Combinatorics (Conference and EMS Summer School, Hungary, 2006) (eds. E., Győ, G., Katona and L., Lovasz), Bolyai Society Mathematical Studies (2008), 105–118.Google Scholar
21. R. L., Graham, B. L., Rothschild and E. G., Straus, Are there n + 2 points in En with odd integral distances?, Amer. Math. Monthly 81 (1974), 21–25.Google Scholar
22. R., Hochberg and P., O'Donnell, Some 4-chromatic unit-distance graphs without small cycles, Geombinatorics V(4) (1996), 137–141.Google Scholar
23. I., Hoffman and A., Soifer, Almost chromatic number of the plane, Geombinatorics III (2) (1993), 38–40.Google Scholar
24. I., Hoffman and A., Soifer, Another six-colouring of the plane, Discrete Math. 150 (1996), 427–429.Google Scholar
25. P. D., Johnson, Jr., Coloring the rational points to forbid the distance one – A tentative history and compendium, Geombinatorics XVI (1) (2006), 209–218.Google Scholar
26. D. G., Larman and C. A., Rogers, The realization of distances within sets in Euclidean space, Mathematika 19 (1972), 1–24.Google Scholar
27. M., Mann, A new bound for the chromatic number of the rational five-space, Geombinatorics XI (2) (2001), 49–53.Google Scholar
28. M., Mann, Hunting unit-distance graphs in rational n-spaces, Geombinatorics XIII (2) (2003), 86–97.Google Scholar
29. L., Moser and W., Moser, Solution to problem 10, Canad. Math. Bull. 4 (1961), 187–189.Google Scholar
30. O., Nechushtan, On the space chromatic number, Discrete Math. 256 (2002), 499–507.Google Scholar
31. P., O'Donnell, High Girth Unit-distance Graphs, Ph.D. thesis, Rutgers University, 1999.Google Scholar
32. M. S., Payne, A unit distance graph with ambiguous chromatic number, arXiv: 0707.1177v1 [math.CO], 9 July 2007.
33. M. S., Payne, Unit distance graphs with ambiguous chromatic number, Electronic J. Combin. 16 (2009).Google Scholar
34. Materialy Konferenzii ‘Poisk-97’, Moscow, 1997 (in Russian).
35. D., Pritikin, All unit-distance graphs of order 6197 are 6-colourable, J. Combin. Theory (B) (1998), 159–163.Google Scholar
36. A. M., Raigorodskii, On the chromatic number of a space, Russian Math. Surveys 55 (2000), 351–352.Google Scholar
37. D. E., Raiskii, Realizing of all distances in a decomposition of the space Rn into n +1 parts, Mat. Zametki 7 (1970), 319–323 (in Russian); English transl., Math. Notes 7 (1970), 194–196.Google Scholar
38. M., Rosenfeld, Odd integral distances among points in the plane, Geombinatorics V (4) (1996), 156–159.Google Scholar
39. S., Shelah and A., Soifer, Axiom of choice and chromatic number of the plane, J. Combin. Theory(A) 103 (2003), 387–391.Google Scholar
40. A., Soifer, Relatives of chromatic number of the plane I, Geombinatorics I (4) (1992), 13–15.Google Scholar
41. A., Soifer, A six-colouring of the plane, J. Combin. Theory (A) 61 (1992), 292–294.Google Scholar
42. A., Soifer, Six-realizable set X6, Geombinatorics III (4) (1994), 140–145.Google Scholar
43. A., Soifer, An infinite class of 6-colorings of the plane, Congr. Numer. 101 (1994), 83–86.Google Scholar
44. A., Soifer, Axiom of choice and chromatic number ofRn, J. Combin. Theory (A) 110 (2005), 169–173.Google Scholar
45. A., Soifer, The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, Springer, 2009.Google Scholar
46. A., Soifer and S., Shelah, Axiom of choice and chromatic number: an example on the plane, J. Combin. Theory (A) 105 (2004), 359–364.Google Scholar
47. R. M., Solovay, A model of set theory in which every set of reals is Lebesgue measurable, Ann. of Math. 92 (1970), 1–56.Google Scholar
48. J., Steinhardt, On coloring the odd-distance graph, Electronic J. Combin. 16 (12) (2009), 1–7.Google Scholar
49. C., Thomassen, On the Nelson unit distance coloring problem, Amer. Math. Monthly 106 (1999), 850–853Google Scholar
50. D. R., Woodall, Distances realized by sets covering the plane, J. Combin. Theory (A) 14 (1973), 187–200.Google Scholar
51. N. C., Wormald, A 4-chromatic graph with a special plane drawing, J. Austral. Math. Soc. (A) 28 (1979), 1–8.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] 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
×