Available in electronic format
Available in print format
Transacrions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

Coloring ${\mathbb R}^n$

Author(s): James H. Schmerl
Journal: Trans. Amer. Math. Soc. 354 (2002), 967-974.
MSC (2000): Primary 03E02, 05C62
Posted: October 31, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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:

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
Email: schmerl@math.uconn.edu

DOI: 10.1090/S0002-9947-01-02881-1
PII: S 0002-9947(01)02881-1
Keywords: Graph coloring, distance graphs, Steinhaus property
Received by editor(s): December 15, 2000
Received by editor(s) in revised form: May 7, 2001
Posted: October 31, 2001
Copyright of article: Copyright 2001, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google