A Note on the Road-Coloring Conjecture

Some results relating to the road-coloring conjecture of Alder, Goodwyn, and Weiss, which give rise to an \(O(n^2)\) algorithm to determine whether or not a given edge-coloring of a graph is a road-coloring, are noted. Probabilistic analysis is then used to show that, if the outdegree of every edge in an \(n\)-vertex digraph is \(\delta = \omega(\log n)\), a road-coloring for the graph exists. An equivalent re-statement of the conjecture is then given in terms of the cross-product of two graphs.