On The Road Coloring Problem

Joel Friedman IBM Almaden and University of California, Berkeley

Last modified: Jan 26, 1989

0 Abstract

Let G = (V, E) be a strongly connected, aperiodic, directed graph having outdegree 2 at each vertex. A red-blue coloring of G is a coloring of the edges with the colors red and blue such that each vertex has one red edge and one blue edge leaving it. Given such a coloring, we define R: V → V by R(v) = w iff there is a red edge from v to w. Similarly we define B: V → V. G is said to be collapsible if some composition of R’s and B’s maps V to a single vertex. The road coloring problem is to determine whether G has a collapsible coloring. It has been conjectured that all such G have a collapsible coloring. Since G has outdegree 2 everywhere and is strongly connected, the adjacency matrix, A, of G has a positive left eigenvector w = (w(v_{1}), …, w(v_{n})) with eigenvalue 2, i.e. wA = 2w. Furthermore, we can assume that w’s components are integers with no common factor. We call w(v) the weight of v. Let W ≡ ∑_{v∈V} w(v), defined to be the weight of the graph. We will prove that if G has a simple cycle of length relatively prime to W, then G is collapsibly colorable.

1 Introduction

Let G = (V, E) be a directed graph. G is said to be strongly connected if any vertex can reach any other vertex by a path in G. G is said to be aperiodic if V cannot be partitioned into d > 1 sets V_{1}, …, V_{d} = V_{0} such that all edges (u, v) with u ∈ V_{i} have v ∈ V_{i+1}.

Let G have outdegree 2 at each vertex. A red-blue coloring of G is a coloring of the edges with the colors red and blue such that each vertex has one red edge and one blue edge leaving it. Given such a coloring, we define R: V → V by R(v) = w iff there is a red edge from v to w. Similarly we define B: V → V. G is said to be collapsible if some composition of R’s and B’s maps V to a single vertex.

The road coloring problem is to determine whether G has a collapsible coloring. It has been conjectured that all such G have a collapsible coloring (i.e. G aperiodic, strongly connected). This problem originated in connection with [2], and appears explicitly in [1]. There it was assumed that G has no multiple edges, i.e. each vertex has edges to two distinct vertices. In [4] it was shown that a graph which has no multiple edges and a simple cycle of prime length is collapsibly colorable. In this paper we analyze a property of noncollapsible colorings; this gives further conditions for collapsible colorability.

Since G has outdegree 2 everywhere and is strongly connected, the adjacency matrix, A, of G has a positive left eigenvector w = (w(v_{1}), …, w(v_{n})) with eigenvalue 2, i.e. wA = 2w. Furthermore, we can assume that w’s components are integers with no common factor. We call w(v) the weight of v. Let W ≡ ∑_{v∈V} w(v), defined to be the weight of the graph. For example, if G has indegree 2 everywhere then W = |V |, the size of V. We will prove that if G has a simple cycle of length relatively prime to W, then G is collapsibly colorable.

I would like to thank Brian Marcus for posing this problem to me and for encouragement on it.

2 An Observation

Let G be a graph as before and fix a coloring of G. For T ⊂ V, let w(T), the wight of T, be the sum of the weights of the vertices in T. We say that T is collapsible if T can be mapped to a single vertex by some composition of R’s and B’s. Let T_{0} be a collapsible set of maximum weight, w_{0}.

Theorem 2.1 There exist i and subsets T_{1}, …, T_{i−1}, each of which is collapsible and of weight w_{0}, such that T_{0}, …, T_{i−1} is a partition of V. In particular, w_{0}i = W.

Proof Let U ⊂ V, and consider its backward images, R^{−1}U, B^{−1}U. Since wA = 2w we have w(R^{−1}U) + w(B^{−1}U) = 2w(U). It follows that either R^{−1}U or B^{−1}U has greater weight than U, or both have weight equal to that of U. Also, if U is collapsible then so are R^{−1}U and B^{−1}U. From these observations it follows that R^{−1} and B^{−1} of any collapsible set of maximum weight is again collapsible of maximum weight.

We have f: T_{0} → v_{0}, where f is a composition of R’s and B’s, and v_{0} ∈ V. Suppose that T_{0} is not all of V. We claim that we can extend f backwards to g = fh, h being a composition of R’s and B’s, so that g maps T_{0} to one vertex and maps another maximum weight collapsible set to another vertex. To see this, consider f^{−1}, which maps V to subsets of V; these subsets form a partition of V. Pick any vertex v ∉ T_{0}, and let g = fhf, where h is any composition of R’s and B’s mapping v_{0} to v. Notice that f(v) ≠ v_{0}, since v ∉ f^{−1}v_{0} since T_{0} is maximal, and that f^{−1}h^{−1}T_{0} is a collapsible set of maximum weight by the preceeding paragraph. It follows that g collapses two disjoint maximum weight collapsible sets. If these two sets do not comprise all of V, then we can extend g backwards to a function which collapses three disjoint maximum weight collapsible sets, one of which is T_{0}, by iterating the same argument. Repeating this process enough times completes the proof of the theorem.

□

A set of vertices U is called a minimal image of V if U is the image of V under some composition of R’s and B’s and if U cannot be reduced in size by any further composition of R’s and B’s. It is easy to see that any such U has size i — any set of size > i must contain at least two points in one of T_{0}, …, T_{i−1} and can therefore be reduced, and set of size < i cannot be the image of a set of vertices of weight > w_{0} times its cardinality, which is less than W.

3 Coloring with Red Trees

Given that G has a simple cycle of length m through vertices v_{0}, … v_{m−1}, we can choose one outgoing edge from each other vertex so that any path through these edges leads to the cycle. Coloring these edges and the edges of the cycle red we get a coloring of G which has a red cycle of length m and a set of red paths taking each vertex into this cycle. We call such colorings of G colorings with red trees (the red edges of G form a tree plus an extra edge to complete the cycle).

The following result appears in O’Brien’s paper —

Theorem 3.1 Let G have a coloring with a red tree and a red cycle of length m. Then i, the size of a minimal image, divides m.

Proof See [4].

□

Combining this with theorem 2.1 we have:

Corollary 3.2 If G is colored with a red tree and a red cycle of length m, m relatively prime to W, then G is collapsible.

Proof Since i divides m and W, i = 1. That is to say G is collapsible.

Corollary 3.3 If W is a prime power, then G is collapsibly colorable.

Proof Since G is aperiodic, G has a cycle relatively prime to p where p is the prime with W = p^{j}. This cycle can be written as the union of simple cycles, and at least one of the simple cycles must be relatively prime to p.

□

In the case where G has indegree 2, has a prime number of vertices, and has no multiple edges, it was previously known that G is collapsibly colorable. This was due to Nelson Markley and Michael Paul, unpublished, based on ideas of G.A. Hedlund in [3].

References

[1] R.L. Adler, L.W. Goodwyn, and B. Weiss. Equivalence of topological markov shifts. Israel J. Math., 27:49–63, 1977.

[2] R.L. Adler and B. Weiss. Similarity of automorphisms of the torus. Memoirs of the AMS, 98, 1970.

[3] G.A. Hedlund. Endomorphisms and automorphisms of the shift. Math. Systems Theory, 3:320–375, 1969.

[4] G.L. O’Brien. The road-colouring problem. Israel J. Math., 39:145–154, 1981.