Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0771.05039
Reid, Michael; Jungreis, Douglas S.; Witte, Dave
Distances forbidden by some two-coloring of $\bbfQ\sp 2$. (English)
[J] Discrete Math. 82, No.1, 53-56 (1990). ISSN 0012-365X

A very famous problem by P. Erd\H{o}s and R. Nelson asks if the points $R\sp 2$ in the plane can be 4-coloured such that no two points of distance 1 are coloured the same. {\it D. R. Woodall} [J. Comb. Theory, Ser. A 14, 187-200 (1973; Zbl 0251.50003)] proved that all the points $\bbfQ\sp 2$ in the plane with rational coordinates can be 2-coloured such that no two points of distance 1 are coloured the same. {\it P. D. Johnson} [Discrete Math. 79, No. 2, 191-195 (1990; Zbl 0701.05005)] extended Woodall's result to 2-colourings of $\bbfQ\sp 2$ where no two points have a distance in certain sets $D$. The main results of the present interesting paper is to show that in a sense Johnson's result is optimal: $\bbfQ\sp 2$ can be 2-coloured with no two points of a distance in $D$ coloured the same if and only if $D$ does not contain two distances $d\sb 1$ and $d\sb 2$ such that (i) $d\sb 1$ and $d\sb 2$ are both distances between points in $\bbfQ\sp 2$, and (ii) there are positive integers $p$ and $q$ with $p+q$ odd such that $d\sb 1/d\sb 2=\sqrt{p/q}$.
[B.Toft (Odense)]

MSC 2000:: *05C15 Chromatic theory of graphs and maps
05C35 Extremal problems (graph theory)
05C12 Distance in graphs

Keywords: two-coloring; rational points; distance

Citations: Zbl 0251.50003; Zbl 0701.05005

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.
	Elementary number theory. Primes, congruences, and secrets.

Simple Search

Zentralblatt MATH Berlin [Germany]