Abstract : The Road Coloring Conjecture is an old and classical conjecture e posed in Adler and Weiss (1970); Adler et al. (1977). 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_v$ of reds and blues such that following the sequence from $\textit{any}$ starting vertex in $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(\log n / \log \log n)$, where $n$ is the number of vertices in the digraph.
Keywords :
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.279-284, 2005, DMTCS Proceedings
Domaine :

Littérature citée [13 références]

https://hal.inria.fr/hal-01184444
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 14:59:12
Dernière modification le : samedi 3 mars 2018 - 01:04:57
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:13:14

### Fichier

dmAE0155.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184444, version 1

### Citation

Rajneesh Hegde, Kamal Jain. A Min-Max theorem about the Road Coloring Conjecture. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.279-284, 2005, DMTCS Proceedings. 〈hal-01184444〉

### Métriques

Consultations de la notice

## 374

Téléchargements de fichiers