11institutetext: Bar-Ilan University, Dep. of Math., 52900, Ramat Gan, Israel

# A Partially Synchronizing Coloring††thanks:
http://www.cs.biu.ac.il/$\sim$trakht

A.N. Trahtman Email<EMAIL_ADDRESS>
###### Abstract

Given a finite directed graph, a coloring of its edges turns the graph into a
finite-state automaton. A $k$-synchronizing word of a deterministic automaton
is a word in the alphabet of colors at its edges that maps the state set of
the automaton at least on $k$-element subset. A coloring of edges of a
directed strongly connected finite graph of a uniform outdegree (constant
outdegree of any vertex) is $k$-synchronizing if the coloring turns the graph
into a deterministic finite automaton possessing a $k$-synchronizing word.

For $k=1$ one has the well known road coloring problem. The recent positive
solution of the road coloring problem implies an elegant generalization
considered first by Béal and Perrin: a directed finite strongly connected
graph of uniform outdegree is $k$-synchronizing iff the greatest common
divisor of lengths of all its cycles is $k$.

Some consequences for coloring of an arbitrary finite digraph are presented.
We describe a subquadratic algorithm of the road coloring for the
$k$-synchronization implemented in the package TESTAS. A new linear
visualization program demonstrates the obtained coloring. Some consequences
for coloring of an arbitrary finite digraph and of such a graph of uniform
outdegree are presented.

Lecture Notes in Computer Science, 6072(2010), 363-370

Keywords: graph, algorithm, synchronization, road coloring, deterministic
finite automaton.

## Introduction

The famous road coloring problem was stated almost 40 years ago [1] for a
strongly connected directed graph of uniform outdegree where the greatest
common divisor (gcd) of lengths of all its cycles is one.

Together with the Černy conjecture [7], [9], the road coloring problem was
once one of the most fascinating problems in the theory of finite automata. In
the popular Internet Encyclopedia ”Wikipedia” it is on the list of most
interesting unsolved problems in mathematics. The recent positive solution of
the road coloring conjecture [10], [13], [11] has posed a lot of
generalizations and new problems.

One of them is $k$-synchronizing coloring. A solution of the problem based on
the method from [11] was appeared first in [4] and repeated later
independently in [5], [12].

Some consequences for coloring of an arbitrary finite digraph as well as for
coloring of such a graph of a uniform outdegree are a matter of our interest.
The minimal value of $k$ for $k$-synchronizing coloring exists for any finite
digraph and therefore a partially synchronizing coloring can be obtained.

Here we describe a polynomial time algorithm for $k$-synchronizing coloring.
Our proof also is based on [11] and [12], the more so the proofs in [4]
meanwhile have some gaps. The theorems and lemmas from [11] are presented
below without proof. The proofs are given only for new or modified results.
The realization of the algorithm is demonstrated by a new linear visualization
program [3]. For an $n$-state digraph with uniform outdegree $d$, the time
complexity of the algorithm is $O(n^{3}d)$ in the worst case and $O(n^{2}d)$
in the majority of cases. The space complexity is quadratic.

## Preliminaries

As usual, we regard a directed graph with colors assigned to its edges as a
finite automaton, whose input alphabet $\Sigma$ consists of these colors.

A directed graph with constant outdegree (the number of outgoing edges) of all
its vertices is called a graph of uniform outdegree.

A finite directed strongly connected graph of uniform outdegree where the gcd
of lengths of all its cycles is $k$ will be called k-periodic.

An automaton is deterministic if no state has two outgoing edges of the same
color. In a complete automaton each state has outgoing edges of any color.

If there exists a path in an automaton from the state $\bf p$ to the state
$\bf q$ and the edges of the path are consecutively labelled by
$\sigma_{1},...,\sigma_{k}\in\Sigma$, then for
$s=\sigma_{1}...\sigma_{k}\in\Sigma^{+}$ let us write ${\bf q}={\bf p}s$.

Let $Ps$ be the map of the subset $P$ of states of an automaton using the word
$s\in\Sigma^{+}$. For the transition graph $\Gamma$ of an automaton let
$\Gamma s$ denote the map of the set of states of the automaton.

Let $|P|$ denote the size of the subset $P$ of states from an automaton (of
vertices from a graph).

A word $s\in\Sigma^{+}$ is called a $k$-synchronizing word of the automaton
with transition graph $\Gamma$ if both $|\Gamma s|=k$ and for all words
$t\in\Sigma^{*}$ holds $|\Gamma t|\geq k$.

A coloring of a directed finite graph is $k$-synchronizing if the coloring
turns the graph into a deterministic finite automaton possessing a
$k$-synchronizing word and the value of $k$ is minimal.

A pair of distinct states $\bf p,q$ of an automaton (of vertices of the
transition graph) will be called synchronizing if ${\bf p}s={\bf q}s$ for some
$s\in\Sigma^{+}$. In the opposite case, if for any $s$ ${\bf p}s\neq{\bf q}s$,
we call the pair deadlock.

A synchronizing pair of states $\bf p$, $\bf q$ of an automaton is called
stable if for any word $u$ the pair of states ${\bf p}u,{\bf q}u$ is also
synchronizing [6], [8].

We call the set of all outgoing edges of a vertex a bunch if all these edges
are incoming edges of only one vertex.

The subset of states (of vertices of the transition graph $\Gamma$) of maximal
size such that every pair of states from the set is a deadlock will be called
an $F$-clique.

##  1 A $k$-synchronizing coloring

###### Lemma 1

Let a finite directed strongly connected graph $\Gamma$ with uniform outdegree
have a $k$-synchronizing coloring. Then the greatest common divisor $d$ of
lengths of all its cycles is not greater than $k$.

If the length of a path from the state $\bf p$ to the state $\bf q$ is equal
to $i\neq 0$ (modulo $d$) then for any word $s$ one has ${\bf p}s\neq{\bf
q}s$.

Proof. Let $N$ be the function defined on the states of $\Gamma$ in the
following way - we take an arbitrary vertex $\bf p$ and let $N({\bf p})=0$.
Then for each vertex $\bf q$ with defined $N({\bf q})$ suppose for any next
nearest vertex $\bf r$ $N({\bf r})=N({\bf q})+1$ (modulo $d$). The graph is
strongly connected, whence for each vertex the function $N$ is defined. The
enumeration does not imply a contradiction anywhere because the length of each
cycle is divided by $d$. Then by any coloring the mapping by a word $t$
produced the same shift of size $|t|$ (modulo $d$) of the function $N$ on the
states. Therefore the states with distinct values of $N$ could not have common
image and $|\Gamma t|\geq d$ for any word $t$. $|\Gamma s|=k$ for
$k$-synchronizing word $s$. Consequently, $k\geq d$.

By any coloring, the mapping by a word $s$ produced the same shift of the
function $N$ on the set of states. $N({\bf p}s)=N({\bf p})+|s|$ (modulo $d$).
Therefore the difference of the values of the function $N$ on two states is
not changed by the shift.

###### Theorem 1.1

[6], [8], [10] Let us consider an arbitrary coloring of a strongly connected
graph $\Gamma$ with constant outdegree. Stability of states is a binary
relation on the set of states of the obtained automaton. Denote the reflexive
closure of this relation by $\rho$. Then $\rho$ is a congruence relation,
$\Gamma/\rho$ presents a directed strongly connected graph with constant
outdegree, the gcd $d$ of all its cycles is the same as in $\Gamma$, and a
$k$-synchronizing coloring of $\Gamma/\rho$ implies a $k$-synchronizing
recoloring of $\Gamma$.

###### Lemma 2

[10] Let $F$ be an $F$-clique via some coloring of a strongly connected graph
$\Gamma$. For any word $s$ the set $Fs$ is also an $F$-clique and each state
[vertex] $\bf p$ belongs to some $F$-clique.

###### Lemma 3

Let $A$ and $B$ ($|A|>1$) be distinct $F$-cliques via some coloring without
stable pairs of the $k$-periodic graph $\Gamma$. Then $|A|-|A\cap
B|=|B|-|A\cap B|>1$.

Proof. Let us assume the contrary: $|A|-|A\cap B|=1$. By the definition of
$F$-clique, $|A|=|B|$ and so $|B|-|A\cap B|=1$, too. Thus $|A|-|A\cap
B|=|B|-|A\cap B|=1$.

The pair of states ${\bf p}\in A\setminus B$ and ${\bf q}\in B\setminus A$ is
not stable. Therefore for some word $s$ the pair $({\bf p}s,{\bf q}s)$ is a
deadlock. Any pair of states from the $F$-clique $A$ and from the $F$-clique
$B$ as well as from $F$-cliques $As$ and $Bs$ is a deadlock. So each pair of
states from the set $(A\cup B)s$ is a deadlock, whence $(A\cup B)s$ is an
$F$-clique.

One has $|(A\cup B)s|=|A|+1>|A|$ in spite of maximality of the size of
$F$-clique $A$.

###### Lemma 4

[10] Let some vertex of a directed complete graph $\Gamma$ have two incoming
bunches. Then any coloring of $\Gamma$ has a stable pair.

Proof. If a vertex ${\bf p}$ has two incoming bunches from vertices ${\bf q}$
and ${\bf r}$, then the pair ${\bf q}$, ${\bf r}$ is stable for any coloring
because ${\bf q}\alpha={\bf r}\alpha=\bf p$ for any letter (color)
$\alpha\in\Sigma$.

###  1.1 The spanning subgraph with maximum of edges in the cycles

###### Definition 1

Let us call a subgraph $S$ of the $k$-periodic graph $\Gamma$ a _s_ panning
subgraph of $\Gamma$ if all vertices of $\Gamma$ belong to $S$ and exactly one
outgoing edge of every vertex (in the usual graph-theoretic terms it is
1-outregular spanning subgraph).

A maximal subtree of the spanning subgraph $S$ with root on a cycle from $S$
and having no common edges with cycles from $S$ is called a _t_ ree of $S$.

The length of the path from a vertex ${\bf p}$ through the edges of its tree
of the spanning set $S$ to the root of the tree is called the _l_ evel of
${\bf p}$ in $S$.

A tree with vertex of maximal level is called a _m_ aximal tree.

###### Remark 1

Any spanning subgraph $S$ consists of disjoint cycles and trees with roots on
cycles. Each tree and cycle of $S$ is defined identically. The level of the
vertices belonging to some cycle is zero. The vertices of the trees except the
roost have a positive level. The vertices of maximal positive level have no
incoming edge in $S$. The edges labelled by a given color defined by any
coloring form a spanning subgraph. Conversely, for each spanning subgraph,
there exists a coloring and a color such that the set of edges labelled with
this color corresponds to this spanning subgraph.

max level 3level 0Cyclelevel 2level 1level 0Tree

###### Lemma 5

Let $N$ be a set of vertices of level $n$ from some tree of the spanning
subgraph $S$ of the $k$-periodic graph $\Gamma$. Then via a coloring of
$\Gamma$ such that all edges of $S$ have the same color $\alpha$, for each
$F$-clique $F$ holds $|F\cap N|\leq 1$.

Proof. Some power of $\alpha$ synchronizes all states of a given level of the
tree and maps them into the root. Each pair of states from an $F$-clique could
not be synchronized and therefore could not belong to $N$.

###### Lemma 6

[10] Let $d$-periodic graph $\Gamma$ have a spanning subgraph $R$ consisting
solely of disjoint cycles (without trees). Then $\Gamma$ either is a cycle of
length $d$ of bunches or has another spanning subgraph with exactly one
maximal tree.

###### Lemma 7

[11] Assume that no vertex of the graph $\Gamma$ has two incoming bunches. Let
$R$ be a spanning subgraph with non-trivial tree and let its tree $T$ with the
root $\bf r$ on cycle $H$ have all vertices of maximal level $L$ and one of
them is the vertex $\bf p$. Let us consider

1) replacing an edge $e$ from $R$ with an edge having the same start vertex as
$e$ and ending in $\bf p$,

2) replacing in $R$ an incoming edge of a root on the path in the tree from
$\bf p$,

3) replacing in $R$ an incoming edge of a root from $H$.

Suppose that at most two such operations do not increase the number of edges
in cycles. Then by the coloring of $R$ by the color $\alpha$ $\Gamma$ has a
spanning subgraph with one maximal tree and the pair ${\bf p}\alpha^{L-1}$,
${\bf p}\alpha^{L+|H|-1}$ is stable.

###### Theorem 1.2

Any $k$-periodic graph $\Gamma$ of size greater than $k$ has a coloring with
stable pair.

Proof. We have $|\Gamma|>k$. By Lemma 4, in the case of vertex with two
incoming bunches $\Gamma$ has a coloring with stable pairs. In opposite case,
by Lemmas 7 and 6, $\Gamma$ has a spanning subgraph $R$ with one maximal tree
in $R$.

Let us give to the edges of $R$ the color $\alpha$ and denote by $C$ the set
of all vertices from the cycles of $R$. Then let us color the remaining edges
of $\Gamma$ by other colors arbitrarily.

By Lemma 2, in a strongly connected graph $\Gamma$ for every word $s$ and
$F$-clique $F$ of size $|F|>1$, the set $Fs$ also is an $F$-clique of the same
size and for any state $\bf p$ there exists an $F$-clique $F$ such that ${\bf
p}\in F$.

In particular, some $F$ has non-empty intersection with the set $N$ of
vertices of maximal level $L$. The set $N$ belongs to one tree, whence by
Lemma 5 this intersection has only one vertex. The word $\alpha^{L-1}$ maps
$F$ on an $F$-clique $F_{1}$ of size $|F|$. One has $|F_{1}\setminus C|=1$
because the sequence of edges of the color $\alpha$ from any tree of $R$ leads
to the root of the tree, and the root belongs to a cycle colored by $\alpha$
from $C$ and only for the set $N$ with vertices of maximal level holds
$N\alpha^{L-1}\not\subseteq C$. So $|N\alpha^{L-1}\cap F_{1}|=|F_{1}\setminus
C|=1$ and $|C\cap F_{1}|=|F_{1}|-1$.

Let the integer $m$ be a common multiple of the lengths of all considered
cycles from $C$ colored by $\alpha$. So for any $\bf p$ from $C$ as well as
from $F_{1}\cap C$ holds ${\bf p}\alpha^{m}={\bf p}$. Therefore for an
$F$-clique $F_{2}=F_{1}\alpha^{m}$ holds $F_{2}\subseteq C$ and $C\cap
F_{1}=F_{1}\cap F_{2}$.

Thus two $F$-cliques $F_{1}$ and $F_{2}$ of size $|F_{1}|>1$ have $|F_{1}|-1$
common vertices. So $|F_{1}\setminus(F_{1}\cap F_{2})|=1$. Consequently, in
view of Lemma 3, there exists a stable pair in the considered coloring.

###### Theorem 1.3

Every strongly connected graph $\Gamma$ is $k$-periodic if and only if the
graph has a $k$-synchronizing coloring. For arbitrary coloring $\Gamma$ is
$m$-synchronizing for $m\geq k$.

Proof. From the $k$-synchronizing coloring of $\Gamma$ by Lemma 1 follows that
if $\Gamma$ is $m$-periodic graph then $m\geq k$. So $|\Gamma|\geq k$. If
$|\Gamma|=k$ then also $m=k$.

Thus we only need to consider the case $|\Gamma|>k$. By Lemmas 6 and 7 there
exists a spanning subgraph with one maximal tree, whence by Theorem 1.2 there
exists a stable pair of states. Theorem 1.1 reduced the problem to a
homomorphic image of $\Gamma$ of smaller size and the induction finishes the
proof.

The theorem 1.3 implies some consequences, in particular, even for an
arbitrary digraph.

###### Lemma 8

Let a finite directed graph $\Gamma$ have a sink component $\Gamma_{1}$.
Suppose that by removing some edges of $\Gamma_{1}$ one obtains strongly
connected directed graph $\Gamma_{2}$ of uniform outdegree. Let $k$ be the
greatest common divisor of lengths of the cycles of $\Gamma_{2}$. Then
$\Gamma$ has $k$-synchronizing coloring.

Proof. $\Gamma_{2}$ has a $k$-synchronizing coloring by Theorem 1.3. The edges
outside $\Gamma_{2}$ can be colored arbitrarily, sometimes by adding new
colors for to obtain deterministic automaton.

###### Lemma 9

Let $\Gamma_{1}$,…, $\Gamma_{m}$ be strongly connected components of a finite
directed graph $\Gamma$ of uniform outdegree such that no edge leaves the
component $\Gamma_{i}$ ($0<i\leq m$). Let $k_{i}$ be the greatest common
divisor of lengths of cycles in $\Gamma_{i}$ and suppose
$k=\sum_{j=1}^{m}k_{j}$. Then $\Gamma$ has $k$-synchronizing coloring.

The Lemmas 8, 9 imply

###### Theorem 1.4

Let finite directed graph $\Gamma$ have a subgraph of uniform outdegree with
strongly connected components $\Gamma_{1}$,…, $\Gamma_{m}$ such that no edge
leaves the component $\Gamma_{i}$ ($0<i\leq m$) in the subgraph. Let $k_{i}$
be the greatest common divisor of lengths of cycles in $\Gamma_{i}$ and
suppose $k=\sum_{j=1}^{m}k_{j}$. Then $\Gamma$ has a $k$-synchronizing
coloring.

The proof for arbitrary $k$ did not use anywhere that $k\neq 1$, whence from
the validity of the Road Coloring Conjecture we have the following:

###### Theorem 1.5

[11] [10] Every finite strongly connected graph $\Gamma$ of uniform outdegree
with greatest common divisor of all its cycles equal to one has synchronizing
coloring.

##  2 Find minimal $k$ for $k$-synchronizing coloring

The algorithm is based on Theorem 1.3 and Lemma 8. One must check the
existence of strongly connected components $(SCC)$ having no outgoing edges to
others $SCC$ and check the condition on gcd in any such $SCC$ $H$. There
exists a subgraph $S$ of $C$ of maximal uniform outdegree. Then we check the
condition on gcd in any such $S$. Let us use the linear algorithm of finding
strongly connected component $SCC$ [2]. Then we mark all $SCC$ having outgoing
edges to others $SCC$ and study only all remaining $SCC$ $H$.

The coloring of $H$: We find in every $H$ the value of $k_{H}$ for the
$k_{H}$-synchronizing coloring of $H$. Let $\bf p$ be a vertex from $H$.
Suppose $d({\bf p})=1$. For an edge ${\bf r}\to{\bf q}$ where $d({\bf r})$ is
already defined and $d({\bf q})$ is not defined suppose $d({\bf q})=d({\bf
r})+1$. If $d({\bf q})$ is defined let us add the difference $abs(d({\bf
q})-1-d({\bf r}))$ to the set $D$ and count the gcd of the integers from $D$.
If finally $gcd=k_{H}$, then the $SCC$ $H$ has $k_{H}$-synchronizing coloring.
The value of $k$ is equal to the sum of all such $k_{H}$ (Theorem 1.3). The
search of $k$ is linear.

The edges outside subgraphs $H$ can be colored arbitrarily (sometimes by
additional colors). The outgoing edges of every state are colored by different
colors.

##  3 The algorithm for $k$-synchronizing coloring

Let us begin from an arbitrary coloring of a directed graph $\Gamma$ with $n$
vertices and $d$ outgoing edges of any vertex. The considered $d$ colors
define $d$ spanning subgraphs of the graph. We find all $SCC$ $H$ having no
outgoing edges and study every such $SCC$ $H$ separately.

We keep images of vertices and colored edges from the generic graph by any
transformation and homomorphism.

If there exists a loop in $\Gamma$ then let us color the edges of a tree with
root in the vertex of a loop by one color. The other edges may be colored
arbitrarily. The coloring in this case is synchronizing for the considered
$SCC$.

In the case of two incoming bunches of one vertex the beginnings of these
bunches form a stable pair by any coloring (Lemma 4). We merge both vertices
in the homomorphic image of the graph (Theorem 1.1) and obtain according to
the theorem a new graph of the size less than $|\Gamma|$.

The linear search of two incoming bunches and of loop can be made at any stage
of the algorithm.

Find the parameters of the spanning subgraph: levels of all vertices, the
number of vertices (edges) in cycles, for any vertex let us keep its tree and
the cycle of the root of the tree. We form the set of vertices of maximal
level and choose from the set of trees a tree $T$ with vertex $\bf p$ of
maximal level. This step is linear and used by any recoloring.

###### Lemma 10

Let graph $\Gamma$ have two cycles $C_{u}$ and $C_{v}$ either with one common
vertex ${\bf p}_{1}$ or with a common sequence ${\bf p}_{1}$,…, ${\bf p}_{k}$,
such that all incoming edges of ${\bf p}_{i}$ form a bunch from ${\bf
p}_{i+1}$ ($i<k$). Let $u\in C_{u}$ and $v\in C_{v}$ be the edges of the
cycles leaving ${\bf p}_{1}$. Let $T$ be a maximal subtree of $\Gamma$ with
the root ${\bf p}_{1}$ and edges from $C_{u}$ and $C_{v}$ except $u$ and $v$.

Then the the adding one of the edges $u$ or $v$ turns the subtree $T$ into
precisely one maximal tree of the spanning subgraph.

Proof. Let us add to $T$ either $u$ or $v$ and then find the maximal levels of
vertices in both cases. The vertex ${\bf p}_{i}$ for $i>1$ could not be the
root of a tree. If any tree of spanning subgraph with vertex of maximal level
has the root ${\bf p}_{1}$ then in both cases the lemma holds. If some tree of
spanning subgraph with vertex of maximal level has the root only on $C_{u}$
then let us choose the adding of $v$. In this case the level of the considered
vertex is growing and only the new tree with root ${\bf p}_{1}$ has vertices
of maximal level. In the case of the root on $C_{v}$ let us add $u$.

1) If there are two cycles with one common vertex then we use Lemma 10 and
find a spanning subgraph $R_{1}$ such that any vertex $\bf p$ of maximal level
$L$ belongs to one tree with root on a cycle $H$. Then after coloring edges of
$R_{1}$ with the color $\alpha$ we find stable pair ${\bf q}={\bf
p}\alpha^{L-1+|H|}$ and ${\bf s}=\bf p\alpha^{L-1}$ (Lemma 7) and go to step
3). The search of a stable pair in this case is linear and the whole algorithm
therefore is quadratic.

2) Let us consider now the three replacements from Lemma 7 and find the number
of edges in cycles and other parameters of the spanning subgraph of the given
color. If the number of edges in the cycles is growing, then the new spanning
subgraph must be considered and the new parameters of the subgraph must be
found. In the opposite case, after at most $3d$ steps, by Lemma 7, there
exists a tree $T_{1}$ with root on the cycle $H_{1}$ of a spanning subgraph
$R_{1}$ such that any vertex $\bf p$ of maximal level $L$ belongs to $T_{1}$.

Suppose the edges of $R_{1}$ are colored by the color $\alpha$. Then the
vertices ${\bf q}={\bf p}\alpha^{L-1+|H_{1}|}$ and ${\bf s}=\bf p\alpha^{L-1}$
by Lemma 7 form a stable pair.

3) Let us finish the coloring and find the subsequent stable pairs of the pair
(${\bf s}$, ${\bf q}$) using appropriate coloring. Then we go to the
homomorphic image $\Gamma_{i}/\rho$ (Theorem 1.1) of the considered graph
$\Gamma_{i}$ ($O(|\Gamma_{i}|m_{i}d)$ complexity where $m_{i}$ is the size of
the map $\Gamma_{i}$). Then we repeat the procedure with a new graph
$\Gamma_{i+1}$ of a smaller size. So the overall complexity of this step of
the algorithm is $O(n^{2}d)$ in the majority of cases and $O(n^{3}d)$ if the
number of edges in cycles grows slowly, $m_{i}$ decreases also slowly, loops
do not appear and the case of two ingoing bunches rarely emerges (the worst
case).

Let $\Gamma_{i+1}=\Gamma_{i}/\rho_{i+1}$ on some stage $i+1$ have
$k$-synchronizing coloring. For every stable pair ${\bf q},{\bf p}$ of
vertices from $\Gamma_{i}$ there exists a pair of corresponding outgoing edges
that reach either another stable pair or one vertex. This pair of edges is
mapped on one image edge of $\Gamma_{i+1}$. So let us give the color of the
image to preimages and obtain in this way a $k$-synchronizing coloring of
$\Gamma_{i}$. This step is linear. So the overall complexity of the algorithm
is $O(n^{3}d)$ in the worst case. If Lemma 10 is applicable, then the
complexity is reduced at this branch of the algorithm (as well as at some
other branches) to $O(n^{2}d)$. The practical study of the implementation of
the algorithm demonstrates mainly $O(n^{2}d)$ time complexity.

##  4 Conclusion

In this paper, we have continued the study of $k$-synchronizing coloring of a
finite directed graph. It is an important and natural generalization of the
well known notion of the synchronizing coloring. This new approach gives an
opportunity to extend essentially the class of studied graphs, removing the
restriction on the size of the great common divisor of the lengths of the
cycles of the graph. The restriction is inspired by the Road Coloring Problem
and now for $k$-synchronizing coloring can be omitted.

There exists still another restriction on the properties of the considered
graphs concerning the uniform outdegree of the vertex. However, it also can be
omitted by consideration of subgraphs of the graph (Corollary 8).

The practical use of this investigation needs an algorithm and the paper
presents a corresponding polynomial time algorithm of the road coloring for
the $k$-synchronization implemented in the package TESTAS. The realization of
the algorithm demonstrates a new linear visualization program [3].

## References

  * [1] R.L. Adler, and B. Weiss, Similarity of automorphisms of the torus, _Memoirs of the Amer. Math. Soc._ , Providence, RI, 98(1970).
  * [2] A. Aho, J. Hopcroft, and J. Ulman. The Design and Analisys of Computer Algorithms, Addison-Wesley 1974.
  * [3] T. Bauer, N. Cohen, and A.N. Trahtman, The visualization of digraph based on its structure properties. _RTAGS_ , Ramat-Gan, Israel, 2007.
  * [4] M.P. Béal, and D. Perrin, A quadratic algorithm for road coloring, arXiv: 0803.0726v2 [cs.DM], 2008.
  * [5] G. Budzban, and P. Feinsilver, The Generalized Road Coloring Problem. arXiv:0903.0192v, [cs.DM], 2008.
  * [6] K. Culik, J. Karhumaki, and J. Kari, A note on synchronized automata and Road Coloring Problem, Developments in Language Theory (5th Int. Conf., Vienna, 2001), _Lecture Notes in Computer Science_ , 2295(2002), 175-185.
  * [7] J. Černy, Poznamka k homogenym eksperimentom s konechnymi automatami, _Math.-Fyz. Čas._ , 14, 1964, 208-215.
  * [8] J. Kari, Synchronizing finite automata on Eulerian digraphs, Springer, _Lect. Notes in Comp. Sci._ , 2136(2001), 432-438.
  * [9] A. Mateescu, and A. Salomaa, Many-valued truth function. Černy conjuncture and road coloring, EATCS Bulletin, 68134-150, 1999.
  * [10] A.N. Trahtman, Synchronizing Road Coloring. _5-th IFIP WCC-TCS_ , Springer, 273(2008), 43-53.
  * [11] A.N. Trahtman, The Road Coloring and Cerny Conjecture. _Proc. of Prague Stringology Conference_ , 2008, 1-12.
  * [12] A.N. Trahtman, The Road Coloring for Mapping on k States. arXiv:0812.4798, 2008 [cs.DM].
  * [13] A.N. Trahtman, The road coloring problem. Israel Journal of Math., v.1, 172(2009), 51-60.