Geometric graphs

doi:10.1017/CBO9781139519793.011

8 - Geometric graphs

Published online by Cambridge University Press: 05 May 2015

Alexander Soifer

Edited by

Lowell W. Beineke and

Robin J. Wilson

Show author details

Alexander Soifer: Affiliation:
University of Colorado
Lowell W. Beineke: Affiliation:
Purdue University, Indiana
Robin J. Wilson: Affiliation:
The Open University, Milton Keynes

Book contents

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

DOI: https://doi.org/10.1017/CBO9781139519793.011 [Opens in a new window]

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

Book contents

8 - Geometric graphs

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive