Unit Distance
Graphs---chromatic number Unit Distance Graphs---girth Barnette's Conjecture Crossing Number of K(7,7) Vertices and Neighbors on a Cycle Square of an Oriented Graph |

A graph which can be embedded in the plane so that vertices correspond to points in the plane and edges correspond to unit-length line segments is called a ``unit-distance graph.'' The question above is equivalent to asking what the chromatic number of unit-distance graphs can be.

Here are some warm-up questions, whose answers are known: What complete bipartite graphs are unit-distance graphs? What's the smallest 4-chromatic unit-distance graph? Show that the Petersen graph is a unit-distance graph.

In this problem, we are interested in finding what sort of unit-distance graphs we can make--in particular, can we find 4-chromatic graphs which have large girth? Paul O'Donnell has found a unit distance graph of girth 12 which cannot be 3-colored, but this graph has an incredibly large number of points. Hochberg and O'Donnell have found 4-chromatic unit-distance graphs of girths 4 and 5 with 23 (shown to the right) and 45 vertices respectively. Are there smaller ones? Are there 4-chromatic unit-distance graphs of arbitrarily large girth? An answer to this question may help to solve the "chromatic number of the plane" problem.

It is known that this is not true if you remove the "bipartite" condition, but the smallest known such graph which is not Hamiltonian has 38 vertices, as shown to the right.

Another way to ask this is the following: If you place 9 red points in the plane and 9 blue points in the plane, and then connect each red point to each blue point with curves (81 curves in all), then what is the minimum number of crossing points that must appear in your drawing?

An example for K(4,4) is shown to the right, with 8 crossings. Actually, this graph can be drawn with just 4 crossings...can you find it?

For these drawings, it is assumed that the curves do not touch the points (vertices) except at their endpoints, and that no three curves meet at a point.

To get the square of an oriented graph (or any directed graph) you leave the vertex set the same, keep all the arcs, and for each pair of arcs of the form (u,v), (v,w), you add the arc (u,w) if that arc was not already present. An example of an oriented graph and its square is shown above.

Here is the open problem: Prove that for every oriented graph, D, there exists a vertex whose out-degree at least doubles when you square the oriented graph. In the example above, the vertices A, B, C, E and G satisfy this property. (For vertices A and G, 2*0=0). Nate learned of this problem from Paul Seymour. David Fisher proved this theorem for tournaments, i.e., orientations of complete graphs.