Distances forbidden by some two-coloring ofQ2

✍ Scribed by Michael Reid; Douglas S. Jungreis; Dave Witte

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 195 KB
• Volume: 82
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(90)90044-i

✦ Synopsis

Let D c R+. A 2-coloring of Cl2 forbids the distances D if for all X, y E Q2, with d(x, y) E D, the two points x and y have different colors. Definition. For any D c R+, we say there is an odd D-cycle (in Q") if there exist Sl, . f * 7 s,EQ'suchthats,+... + s, = 0 (under componentwise addition), ]lsil] E D for each i, and n is odd. (Not having an odd D-cycle means a certain subset of CP2 is "weakly two-free", in the language of [l, 21.)

The following lemma follows from the fact that a graph is bipartite iff it contains no odd cycle.