As it turns out, there are several different versions of the problem, depending on our assumptions. Is the arrangement simple (containing no three lines that meet at a single point)? Do we count as edges the connections that wrap around "through infinity" connecting the first and last crossings on each line? We might also ask whether we allow parallel lines or not, but unlike the previous two questions this does not seem to be important in determining the chromatic number of line arrangements.
To see this, note that any simple arrangement forms a graph in which each vertex has exactly four neighbors. A well-known result in graph theory (Brooks' theorem) states that if the vertices in a graph have at most k neighbors, and the graph is neither complete nor an odd cycle, then the graph is k-colorable. In our case, an odd cycle clearly has fewer than four neighbors per vertex, so the only other problem case would be the complete graph K5. And although K5 can be embedded on the projective plane (one embedding is shown below) it can not come from a line arrangement, since its does not have a triangular number of vertices. (A simple n-line arrangement has exactly n(n-1)/2 vertices.)
So Brooks' theorem tells us that four colors suffice to color simple arrangements with wraparound. The following example shows a matching lower bound: at least four colors may be required.
This graph's vertices have odd numbers of neighbors so it does not come from a line arrangement. The following example (known in projective geometry as the "complete quadrangle") shows that five colors may sometimes be needed for the graphs coming fromline arrangements. The three outer vertices and the center one are all connected to each other, and so require four different colors. The remaining three vertices are each connected to these four and require a fifth color.
We now sketch a proof that five colors are always sufficient. A line arrangement always has a degree-four vertex (Sylvester's theorem); this can be seen by applying Euler's formula to show that there exists a vertex of degree at most five, but then observing that all vertex degrees are even. So, let v be such a vertex, contained on line L.
Form a graph G by collapsing all vertices on line L into a single point; then G is a planar graph. More technically, L can be assumed to be the "line at infinity" of the projective plane, and the collapse of L produces the "one-point completion" of the Euclidean plane, which is just a sphere, and graphs embedded on the sphere are always planar. So by the four-color theorem G can be colored with at most four colors.
If we undo the collapse, to get back to the line arrangement we're interested in coloring, then everything on L will be colored the same color, say red, L will have no red neighbors, and the rest of the arrangement will be colored ok. We now recolor the vertices on L to make a five-coloring of the whole arrangement. Because we've only used four colors so far, one color, say blue, is still unused. The vertices on L form a cycle, which can be thought of as a path connected at its endpoints by the special vertex v. We simply change the color of every other vertex on that path from red to blue. Finally, we need to choose a color for v. If L has an odd number of vertices, one neighbor of v on L might be red and one might be blue. But only two of the three remaining colors can be used by the other two neighbors of v, so there is always some color available to color v and complete the five-coloring of the arrangement.
From the Geometry Junkyard,
and recreational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.
Last update: .