| author: | Rajneesh Hegde and Kamal Jain |
|---|---|
| title: | A Min-Max 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
out-degree 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 min-max
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 Min-Max 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 Min-Max 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. 279-284 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dmAE0155.ps.gz (49 K) |
| ps-source: | dmAE0155.ps (120 K) |
| pdf-source: | 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.