04057518

a

04057518 Johnson, P.D.jun. Two-colorings of real quadratic extensions of $Q\sp 2$ that forbid many distances. Combinatorics, graph theory, and computing, Proc. 18th Southeast. Conf., Boca Raton/Fl. 1987, Congr. Numerantium 60, 51-58 (1987). 1987 EN forbidden distances weakly 2-free sets Abelian group coloring Cayley graph Zbl 0638.00009 [For the entire collection see Zbl 0638.00009.] For an Abelian group $(A,+,0)$ with $S\subseteq A$ the set S is called weakly two-free if $\sum\sp{k}\sb{i=1}m\sb is\sb i\ne 0$ whenever $s\sb 1,...,s\sb k\in S$ and $m\sb 1,...,m\sb k$ are integers such that $\sum\sp{k}\sb{i=1}m\sb i$ is odd (*). A coloring of A forbids S if and only if, for all $a\in A$ and $s\in S$, a and $a+s$ have different colors (**). Let $G=G(A,S)$ be the Cayley graph, whose vertices are in A, and in which a,b$\in A$ are adjacent if and only if a-b$\in S\cup (-S).$ Then (*) says that S is weakly two-free if and only if there is no walk of odd length in G starting and ending at 0. Definition (**) says that a coloring of A forbids S if it is an admissible vertex-coloring of G. The content of the paper is the proof of the following theorem: Suppose that m is a squarefree positive integer, and $m\equiv 1$ mod 4 or $m\equiv 2$ mod 4. Then [Q($\sqrt{m})]$ 2 is two-colorable so that all the distances $\sqrt{p/q}$, p, q odd positive integers, are forbidden. Further, the author poses some problems arising from this theorem. U.Baumann