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.