The use of Nash’s Hex lemma in my previous post, according to which any 2-coloring of a triangular grid has a long monochromatic path, naturally raises the question: for which graphs other than the triangular grid is this true? In that post I mentioned that it is also true for certain outerplanar graphs, but false for bipartite graphs and for subcubic graphs. Here’s another class of graphs for which it is false: the graphs of bounded pathwidth. These graphs can always be 2-colored in a way that breaks up all long paths, leaving the remaining monochromatic paths of bounded size.

Rather than dealing with pathwidth directly, I want to formulate it geometrically in terms of interval graphs. Every graph can be completed (by adding extra edges) to form an interval graph of the same pathwidth; an interval graph has one-dimensional closed intervals as its vertices, connected by an edge whenever they intersect. The pathwidth of an interval graph is always one less than the maximum number of intervals that overlap at the same point (their ply). So rather than looking at graphs of bounded pathwidth I’ll be considering sets of intervals of bounded ply. For example in the illustration below which I drew a few years ago for Wikipedia, the intervals shown have ply 3, and their interval graph has pathwidth 2.

A set of intervals and their associated interval graph

Intervals with low ply that are all either nested or disjoint can have no long paths in their intersection graph regardless of coloring. In any set of intervals forming a path, the path can pass through the outermost level of nesting at most once, subdividing it into two smaller paths with lower ply. It follows by induction the number of intervals in the path can be at most \(2^{\operatorname{ply}}-1\). (This is the standard argument behind an equivalence in graphs between longest path length and tree-depth.) So if we could partition an arbitrary set of intervals into two subsets within which all intervals are nested or disjoint, we’d be done. For instance, in the example above, the partition into \(\{A,B,F\}\) and \(\{C,D,E,G\}\) works. Not every set of intervals can be partitioned in this way, but I’ll show below that it’s always possible to lengthen some intervals, keeping the ply small, so that the lengthened intervals can be partitioned (colored) into two nested subsets.

As a subroutine in the construction, let’s find a set of points with the following properties:

  • Each interval lies strictly between the leftmost and rightmost selected points.

  • No interval covers more than one selected point.

  • The union of the intervals that cover selected points equals the union of all the intervals.

This can be done by a greedy algorithm that repeatedly selects an uncovered interval endpoint until the intervals that cover selected points also cover all other interval endpoints. Finish by selecting any two points to the left and right of all the intervals, and then number the selected points as \(x_0,x_1,\dots\) in left-to-right order. For example, one possible choice for our example would have \(x_0\) to the left of the intervals, \(x_1\) at the left endpoint of \(D\), \(x_2\) at the left endpoint of \(F\), and \(x_3\) to the right of the intervals. For this choice, \(B\) and \(E\) do not cover any selected points, but that’s not a problem. It’s not necessary to optimize how many points are selected.

Call an interval “odd” if it covers an odd-numbered point \(x_i\) and “even” if it covers an even-numbered point. In our example, \(A\), \(C\), and \(D\) are odd, and \(F\), and \(G\) are even, but \(B\) and \(E\) are neither odd nor even. We will color the odd intervals blue and the even intervals red. Because they are different colors, we don’t have to worry about nesting between odd and even intervals. However, the intervals that contain any single point \(x_i\) will have the same color and need to be lengthened to nesting intervals. To do so, we extend all these intervals to a single longer interval, from just after \(x_{i-1}\) to just before \(x_{i+1}\). Because of the way the points \(x_i\) were chosen, this does not create new intersections between intervals of the same color, and it makes all colored intervals nest with all uncolored ones (not just with each other). However, it can also increase the ply. If the ply was \(p\) previously, it can increase by as much as \(2p-1\), when a point that was previously covered by only one odd or even interval becomes covered by \(2p-1\) more of them.

Finally, we apply the same coloring and lengthening process recursively, to the remaining subsets of uncolored intervals between each pair of selected points. To make sure the intervals stay nested after lengthening, we take care in each recursive subproblem to select its first and last points to be inside all intervals of the outer problem that contain the subproblem. Because every point in an interval of a recursive subproblem is also in at least one of the outer colored intervals, the recursive subproblem has smaller ply than the initial ply of the outer problem. The recursion stops at ply 2; for this ply the intersection graph is a tree (more precisely a caterpillar) and it is possible to 2-color the intervals without any lengthening so that no two intervals of the same color intersect, by 2-coloring the tree.

So if we start with intervals of ply 2, we produce a lengthened, 2-colored, and monochromatically nested set of intervals of ply 2 again (no change to the ply). If we start with intervals of ply 3, we produce a lengthened, 2-colored, and monochromatically nested set of intervals of ply at most 8, because the ply-3 interval-lengthening process added at most 5 to the existing ply. More generally for any starting ply \(p\) the new ply will be at most \(p^2+p-4\). And since the interval graph for the lengthened intervals has no monochromatic path with more than \(2^{p^2+p-4}-1\) intervals in it, neither does the interval graph for the original intervals, with the same 2-coloring.

(Discuss on Mastodon)