Article
Full entry |
PDF
(1.2 MB)
Feedback
PDF
(1.2 MB)
Feedback
Keywords:
vertex colouring; infinity graph; decomposition of the real plane
vertex colouring; infinity graph; decomposition of the real plane
Summary:
What is the least number of colours which can be used to colour all points of the real Euclidean plane so that no two points which are unit distance apart have the same colour? This well known problem, open more than 25 years is studied in the paper. Some partial results and open subproblems are presented.
References:
[1] R. B. Eggleton P. Erdös D. K. Skilton: Colouring the real line. J. Comb. Theory Ser. B 39 (1985), 86-100. DOI 10.1016/0095-8956(85)90039-5 | MR 0805458
[2] P. Erdös: Some unsolved problems. Publ. Math. Inst Hung. Acad. Sci. 6 (1961), 221-254. MR 0177846
[3] P. Erdös F. Harary W. T. Tutte: On dimension of a graph. Mathematika 12 (1965), 118-122. DOI 10.1112/S0025579300005222 | MR 0188096
[4] P. Erdös: On combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25-42. DOI 10.1007/BF02579174 | MR 0602413
[5] P. Frankl: Extremal problems and coverings of the space. European J. Comb. I (1980), 101-106. DOI 10.1016/S0195-6698(80)80045-X | MR 0587524 | Zbl 0463.05043
[6] H. Hadwiger: Ungelöste Probleme No. 40. Elemente der Math. 16 (1961), 103-104. MR 0133734
[7] H. Hadwiger H. Debrunner V. Klee: Combinatorial Geometry in the Plane. Holt, Reinehart and Winston, New York (1964). MR 0164279
[8] D. G. Larman C. A. Rogers: The realization of distances within sets in Euclidean space. Mathematika 19 (1972), 1-24. DOI 10.1112/S0025579300004903 | MR 0319055
[9J L. Moser W. Moser: Solution to Problem 10. Canad. Math. Bull. 4 (1961), 187-189. DOI 10.1017/S1446788700014865
[10] N. Wormald: A 4-chromatic graph with a special plane drawing. J. Austral. Math. Soc. Ser. A 28 (1979), 1-8. MR 0541161 | Zbl 0418.05026
Search
Partner of
