# Graph Theory Open Problems

Index of Problems

### Unit Distance Graphs---chromatic number

RESEARCHER: Robert Hochberg
OFFICE: CoRE 414
Email:hochberg@dimacs.rutgers.edu
DESCRIPTION: How many colors are needed so that if each point in the plane is assigned one of the colors, no two points which are exactly distance 1 apart will be assigned the same color? This problem has been open since 1956. It is known that the answer is either 4, 5, 6 or 7---this is not too hard to show. You should try it now in order to get a flavor for what this problem is really asking. This number is also called ``the chromatic number of the plane.''

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. ### Unit Distance Graphs---girth RESEARCHER: Robert Hochberg
OFFICE: CoRE 414
Email:hochberg@dimacs.rutgers.edu
DESCRIPTION: As the problem mentioned above remains unsolved, mathematicians have turned their attention to related problems in the hopes of gaining some insight into this difficult question.

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. ### Barnette's Conjecture RESEARCHER: Peter Hamburger
OFFICE: CoRE 442
Email:hamburge@dimacs.rutgers.edu
DESCRIPTION: Is it true that every 3-connected, 3-regular, planar bipartite graph is Hamiltonian?

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. ### Crossing Number of K(7,7) RESEARCHER: Robert Hochberg
OFFICE: CoRE 414
Email:hochberg@dimacs.rutgers.edu
DESCRIPTION: What is the crossing number of the complete bipartite graph K(7,7)? It is known that the answer is either 77, 79 or 81.

Another way to ask this is the following: If you place 7 red points in the plane and 7 blue points in the plane, and then connect each red point to each blue point with curves (49 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. ### Vertices and Neighbors on a Cycle RESEARCHER: Nate Dean
OFFICE: 2A-403, Bell Labs, Murray Hill
Email:nate@dimacs.rutgers.edu
DESCRIPTION: Is it true that every k-connected (k>1) graph which does not have a Hamiltonian cycle has a cycle that contains k independent vertices and their neighbors? This is known to be true for k = 2 and 3. For example, the graph to the right is 3-connected but not Hamiltonian. And the dotted cycle shown contains 3 independent vertices (the three vertices which are lighter in color) and thier neighbors. To see that it is not Hamiltonian, notice that this graph is just the complete bipartite graph K(3,4). ### The Square of a Directed Graph

RESEARCHER: Nate Dean OFFICE: 2A-403, Bell Labs, Murray Hill
Email:nate@dimacs.rutgers.edu
DESCRIPTION: This problem deals with the "square of an oriented graph." An oriented graph is a simple graph (no loops or multiple edges) in which each edge is replaced by an arc. Thus you produce a simple directed graph without pairs of "reversed arcs."

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.