2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Stefan Felsner (ed.)
DMTCS Conference Volume AE (2005), pp. 279284
author:  Rajneesh Hegde and Kamal Jain 

title:  A MinMax theorem about the Road Coloring Conjecture 
keywords:  road coloring, synchronization of automata 
abstract: 
The Road Coloring Conjecture is an old and classical
conjecture posed in [adler70,adler77]. Let
G
be a strongly connected digraph with uniform
outdegree 2. The Road Coloring Conjecture states that,
under a natural (necessary) condition that
G
is ``aperiodic'', the edges of
G
can be colored red and blue such that ``universal
driving directions'' can be given for each vertex. More
precisely, each vertex has one red and one blue edge
leaving it, and for any vertex
v
there exists a sequence
s
of reds and blues such that following the sequence
from any starting vertex in
v
G
ends precisely at the vertex
v
. We first generalize the conjecture to a minmax
conjecture for all strongly connected digraphs. We then
generalize the notion of coloring itself. Instead of
assigning exactly one color to each edge we allow multiple
colors to each edge. Under this relaxed notion of coloring
we prove our generalized MinMax theorem. Using the Prime
Number Theorem (PNT) we further show that the number of
colors needed for each edge is bounded above by
O(
, where
log
n/
log
log
n)
n
is the number of vertices in the digraph.

If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files.  
reference:  Rajneesh Hegde and Kamal Jain (2005), A MinMax theorem about the Road Coloring Conjecture, in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), Stefan Felsner (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AE, pp. 279284 
bibtex:  For a corresponding BibTeX entry, please consider our BibTeXfile. 
ps.gzsource:  dmAE0155.ps.gz (49 K) 
pssource:  dmAE0155.ps (120 K) 
pdfsource:  dmAE0155.pdf (141 K) 
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.
Automatically produced on Di Sep 27 10:09:57 CEST 2005 by gustedt