Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Coloring ${\mathbb R}^n$

Author: James H. Schmerl
Journal: Trans. Amer. Math. Soc. 354 (2002), 967-974
MSC (2000): Primary 03E02, 05C62
Published electronically: October 31, 2001
MathSciNet review: 1867367
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: If $1 \leq m \leq n$ and $A \subseteq {\mathbb R}$, then define the graph $G(A,m,n)$ to be the graph whose vertex set is ${\mathbb R}^n$ with two vertices $x,y \in {\mathbb R}^n$ being adjacent iff there are distinct $u,v \in A^m$ such that $\Vert x-y\Vert = \Vert u-v\Vert$. For various $m$ and $n$ and various $A$, typically $A = {\mathbb Q}$ or $A = {\mathbb Z}$, the graph $G(A,m,n)$ can be properly colored with $\omega$ colors. It is shown that in some cases such a coloring $\varphi : {\mathbb R}^n \longrightarrow\omega$ can also have the additional property that if $\alpha : {\mathbb R}^m \longrightarrow{\mathbb R}^n$ is an isometric embedding, then the restriction of $\varphi$ to $\alpha(A^m)$ is a bijection onto $\omega$.

References [Enhancements On Off] (What's this?)

  • 1. P. Erdos, Problems and results in chromatic graph theory, in: Proof Techniques in Graph Theory, (F. Harary, ed.), Academic Press, 1969, pp. 27-35. MR 40:5494
  • 2. P. Erdos and P. Komjáth, Countable decompositions of ${\mathbb R}^2$and ${\mathbb R}^3$, Discrete & Comp. Geom. 5 (1990), 325-331. MR 91b:04002
  • 3. S. Jackson and R.D. Mauldin, On a lattice problem of H. Steinhaus (preprint, Feb., 2001).
  • 4. P. Komjáth, A lattice-point problem of Steinhaus, Quarterly J. of Math. 43 (1992), 235-241. MR 93c:04003
  • 5. P. Komjáth, A decomposition theorem for ${\mathbb R}^n$, Proc. Amer. Math. Soc. 120 (1994), 921-927. MR 94h:04005
  • 6. P. Komjáth, A coloring result for the plane, J. Appl. Anal. 5 (1999), 113-117. MR 2000f:03138
  • 7. J.H. Schmerl, Countable partitions of Euclidean space, Math. Proc. Cambridge Phil. Soc. 120 (1996), 7-12. MR 96k:52011

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03E02, 05C62

Retrieve articles in all journals with MSC (2000): 03E02, 05C62

Additional Information

James H. Schmerl
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269-3009

Keywords: Graph coloring, distance graphs, Steinhaus property
Received by editor(s): December 15, 2000
Received by editor(s) in revised form: May 7, 2001
Published electronically: October 31, 2001
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society