Planar unit-distance graphs having planar unit-distance complement

A graph G=(V,E) is called a unit-distance graph in the plane if there is an embedding of V into the plane such that every pair of adjacent vertices are at unit distance apart. If an embedding of V satisfies the condition that two vertices are adjacent if and only if they are at unit distance apart, then G is called a strict unit-distance graph in the plane. A graph G is a (strict) co-unit-distance graph, if both G and its complement are (strict) unit-distance graphs in the plane. We show by an exhaustive enumeration that there are exactly 69 co-unit-distance graphs (65 are strict co-unit-distance graphs), 55 of which are connected (51 are connected strict co-unit-distance graphs), and seven are self-complementary.     

Tearing a strip off the plane

In this article we examine some homomorphic properties of certain subgraphs of the unit-distance graph. We define G_r to be the subgraph of the unit-distance graph induced by the subset (−∞, ∞) × [0, r] of the plane. The bulk of the article is devoted to examining the graphs G_r, when r is the minimum width such that G_r contains an odd cycle of given length. We determine for each odd n the minimum width r_n such that contains an n-cycle C_n, and characterize the embeddings of C_n in $G_{r_{n}}$. We then show that is homomorphically equivalent to C_n when n ≡ 3 (mod 4), but is a core when n ≡ 1 (mod 4). We begin by showing that G_r is homomorphically compact for each r ≥ 0, as defined in [1]. We conclude with some other interesting results and open problems related to the graphs G_r. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 17–33, 1998     

The Odd-Distance Plane Graph

The vertices of the odd-distance graph are the points of the plane ℝ². Two points are connected by an edge if their Euclidean distance is an odd integer. We prove that the chromatic number of this graph is at least five. We also prove that the odd-distance graph in ℝ² is countably choosable, while such a graph in ℝ³ is not. The research of J. Maňuch was supported in part by MITACS (Mathematics of Information Technology and Complex Systems). The research of M. Rosenfeld was supported in part by the Chancellor Research Grant and the Institute of Technology, UWT. The research of S. Shelah was supported by the United States-Israel Binational Science Foundation (Grant no. 2002323), and by NSF grant No. NSF-DMS 0600940. No. 923 on Shelah’s publication list. The research of L. Stacho was supported in part by NSERC (Natural Science and Engineering Research Council of Canada) grant.