DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large
DMTCS Conference vol AE (2005), pp. 279-284


2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Stefan Felsner (ed.)

DMTCS Conference Volume AE (2005), pp. 279-284

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
be a strongly connected digraph with uniform out-degree 2. The Road Coloring Conjecture states that, under a natural (necessary) condition that
is ``aperiodic'', the edges of
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
there exists a sequence
of reds and blues such that following the sequence from any starting vertex in
ends precisely at the vertex
. 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
, where
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: (49 K)
ps-source: (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.

Automatically produced on Di Sep 27 10:09:57 CEST 2005 by gustedt

Valid XHTML 1.0 Transitional