A 'Road Coloring' Problem

This is on the July 2003 challenge at the Ponder This column at IBM Research. See here for the statement of the problem.

This problem is stated to be still open. Here we (N. Ramana Rao and self)look at a special case thereof.

1. We look at the special case of Road Coloring where at least one of the cities has an outgoing road ending in the same city. Suppose there are N cities, and Cx be any of the cities which have road to itself. We do the following visualization:

Keep Cx at the center and arrange the other cities in layers around it. First keep those cities which have roads directly leading to Cx to Cx in the first layer around Cx. Call this layer L1. Now keep the cities which have roads directly leading to cities of L1 in the next layer L2. Thus we keep all the cities in layers around Cx.

The coloring:
For every other city C, there is at least one outgoing road leading into the layer just inside of the layer on which C lies. Color this road from C to its next inner layer red. The other outgoing road from C is colored green. If both roads from C lead to the next inner layer, either may be colored red or green. For the central city Cx, the self-reaching loop road should be red.

With this coloring, one has a constant and finite path leading from ANY city to the central city Cx. This sequence of roads to the central city is always of the form of one Green followed by as many Reds as there are layers (an example is given below).

For any specified city C', there exists a fixed path from central city Cx to it (guaranteed in problem statement). So given any destination C', starting at any unknown source C, we can by first taking the constant path to the center and the path from center to C'. The path will be the same for any starting city C and will depend only on destination C'.

Example:

There are 5 cities numbered 1 to 5. arranged in a pentagon and connected clockwise. 1, 2, 4 and 5 have one road each that loops back on itself. 3-5 is another road.

ie, the roads are 1-2, 2-3, 3-4, 4-5, 5-1, 1-1, 2-2, 3-5, 4-4, 5-5

there are two cycles 1-2-3-5 (length 4) and 1-2-3-4-5 (length 5) - the lengths are relatively prime. As far as we can make out, this property is not used in what follows...

We choose 1 as the central city. The next layer has only 5 (since only from 5 is there a direct path to 1) In the next layer there are two cities, 3 and 4 In the outermost layer there is only 2.

By above coloring scheme, 2-3, 3-5, 4-5, 5-1, and 1-1 should be red and the others roads are green.

The seqeunce GRRR takes you to city 1 from any starting city. Once we have a samepath to the central city from anywhere we also have a same path to any required destination from anywhere.