Road coloring problem

Road coloring problem

In graph theory the road coloring theorem, known until recently as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network (which might be a representation of city streets or a maze). [cite news | last =Seigel-Itzkovich | first =Judy | title =Russian immigrant solves math puzzle | pages = | publisher =The Jerusalem Post | date = 2008-02-08 | url = | accessdate = 2008-03-21] In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics.

The theorem was first conjectured in 1970 by Benjamin Weiss and Roy Adler.R.L. Adler, B. Weiss. Similarity of automorphisms of the torus. Memoires of the American Mathematical Society, Vol 98. 1970.] It was proved by Avraham Trahtman in September 2007. [cite web | last =Trahtman | first =Avraham | title =The road coloring problem | url= | accessdate = 2008-03-21]

Example and intuition

The image to the right shows a directed graph on eight vertices in which each vertex has out-degree 2. (Each vertex in this case also has in-degree 2, but that is not necessary for a synchronizing coloring to exist.) The edges of this graph have been colored red and blue to create a synchronizing coloring.

For example, consider the vertex marked in yellow. No matter where in the graph you start, if you traverse all nine edges in the walk "blue-red-red—blue-red-red—blue-red-red", you will end up at the yellow vertex. Similarly, if you traverse all nine edges in the walk "blue-blue-red—blue-blue-red—blue-blue-red", you will always end up at the vertex marked in green, no matter where you started.

The road coloring theorem states that for a certain category of directed graphs, it is always possible to create such a coloring.

Mathematical description

Let "G" be a finite directed graph where all the vertices have the same out-degree "k". Let "A" be the alphabet containing the letters 1, ..., "k". A "synchronizing coloring" (also known as a "collapsible coloring") in "G" is a labeling of the edges in "G" with letters from "A" such that (1) each vertex has exactly one outgoing edge with a given label and (2) for every vertex "v" in the graph, there exists a word "w" over "A" such that all paths in "G" corresponding to "w" terminate at "v".

The terminology "synchronizing coloring" is due to the relation between this notion and that of a synchronizing word in finite automata theory.

For such a coloring to exist at all, it is necessary that "G" be both strongly connected and aperiodic. [] The road coloring problem states that these two conditions are also "sufficient" for such a coloring to exist. Therefore, the road coloring problem can be stated briefly as:

:"Every finite strongly-connected aperiodic directed graph of uniform out-degree has a synchronizing coloring."

Previous partial results

Previous partial or special-case results include the following:

*If "G" is a finite strongly-connected aperiodic directed graph with no multiple edges, and "G" contains a simple cycle of prime length which is a proper subset of "G", then "G" has a synchronizing coloring. (O'Brien 1981)

*If "G" is a finite strongly-connected aperiodic directed graph (multiple edges allowed) and every vertex has the same in-degree and out-degree "k", then "G" has a synchronizing coloring. (Kari 2003)


*Jarkko Kari, "Synchronizing finite automata on Eulerian digraphs", "Theoretical Computer Science" 295 (2003), 223–232.
* G. L. O'Brien, "The road-coloring problem", "Israel Journal of Mathematics", Vol. 39, 1981.

ee also

* Four color theorem
* Graph coloring


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • Avraham Trahtman — Infobox Scientist name = Avraham Trahtman box width = | image width = caption = birth date = birth place = death date = death place = residence = Jerusalem, Israel citizenship = nationality = ethnicity = field = Mathematics work institutions =… …   Wikipedia

  • Aperiodic graph — In the mathematical area of graph theory, a directed graph is said to be aperiodic if there is no integer k > 1 that divides the length of every cycle of the graph. Equivalently, a graph is aperiodic if the greatest common divisor of the lengths… …   Wikipedia

  • Synchronizing word — This drawing represents a DFA with eight states and two input symbols, red and blue. The word blue red red blue red red blue red red is a synchronizing word that sends all states to the yellow state; the word blue blue red blue blue red blue blue …   Wikipedia

  • Трахтман, Абрам Наумович — В Википедии есть статьи о других людях с такой фамилией, см. Трахтман. Абрам Наумович Трахтман Дата рождения …   Википедия

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Открытые математические проблемы — Открытые (нерешённые) математические проблемы  проблемы, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна… …   Википедия

  • Liste de conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, non exhaustive. Elles sont divisées en quatre sections, en accord avec leur état en 2011. Voir aussi : Conjecture d Erdős (en), qui liste des conjectures de Paul Erdős et de ses… …   Wikipédia en Français

  • Network (mathematics) — In graph theory, a network is a digraph with weighted edges. These networks have become an especially useful concept in analysing the interaction between biology and mathematics. Using networks of all types; various applications based on the… …   Wikipedia

  • Синхронизируемое слово — «»В компьютерной науке, точнее, в теории детерминированных конечных автоматов (ДКА), синхронизирующее слово (или сжимающая последовательность) во входном алфавите автомата отображает все его состояния в одно и то же состояние[1]. То есть, если… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”