Geometric graphs
Joseph Zaks (Università di Haifa)

Let F be s subfield of the reals, and let F^d be the linear d-space spanned by the points of E^d which have their coordinates in the field F. Let G(F,d,r) be the graph on F^d as its vertex set, and where x is connected by an edge to y if |x - y| = r.

There is a long standing open problem about the chromatic number X(G(R,2,1)), known to be between 4 and 7. The rational case satisfies X(G(Q,2,1)=X(G(Q,3,1) = 2 and X(G(Q,4,1))=4. Only asymptotic bounds are known for X(G(R,d,1)) and X(G(Q,d,1)) for higher values of d.

It is known that G(Q,d,1) is connected if, and only if, d >= 5.

One may wonder when is G(Q,d*,r) isomorphic to G(Q,d**, s), in the non-trivial cases where r/s is not a rational number, and r2 and s2 are rationals.

Another property that was treated is the clique number w of G(F,d,r); w(G(Q,d,1)) has been completely determined.