Cycles of relatively prime length and the road coloring problem (Q5939288): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Equivalence of topological Markov shifts / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Similarity of automorphisms of the torus / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Road Coloring Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3838420 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The road-colouring problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Codes asynchrones / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4037012 / rank | |||
Normal rank |
Revision as of 18:55, 3 June 2024
scientific article; zbMATH DE number 1625485
Language | Label | Description | Also known as |
---|---|---|---|
English | Cycles of relatively prime length and the road coloring problem |
scientific article; zbMATH DE number 1625485 |
Statements
Cycles of relatively prime length and the road coloring problem (English)
0 references
17 February 2002
0 references
A directed graph \(G=(V,E)\) is given in such a way that each outdegree is \(k\). We label each edge of \(G\) with one of \(k\) labels in such a way that for each vertex \(v\) and each label \(l\) there is a unique edge \(e\) leaving \(v\) and having label \(l\). Such a labeling is said to be a synchronizing coloring of \(G\) if there is a certain sequence \((l_1,l_2,\ldots,l_m)\) of labels, so that for any vertex \(v\) of \(G\) the walk that starts from \(v\) and follows the edges labeled with \(l_1,l_2,\ldots,l_m\) always ends at the very same vertex \(w\) of \(G\), independently of \(v\). The road coloring problem is to find a synchronizing coloring for a given graph \(G\) as above. Clearly, a synchronizing coloring cannot exist if \(G\) is periodic, that is \(V\) can be partitioned into parts \(V_1,V_2,\ldots,V_p\) so that each edge goes from some \(V_i\) to the next part \(V_{i+1}\) (addition is modulo \(p\)). It is generally believed that for any aperiodic graph (a graph that is not periodic, or in other words, a graph that contains some directed cycles that have relatively prime length) there always exists some synchronizing coloring. The paper justifies this belief for certain classes of graphs. The basic idea is to find label-sequences for a given labeling that ensure that the corresponding path ends on a certain cycle. As a corollary a related earlier result of \textit{N. Jonoska} and \textit{S. Suen} [Monocyclic decomposition of graphs and the road coloring problem, Congr. Numerantium 110, 201-209 (1995; Zbl 0905.05066)] is deduced. The proof of the most general condition involves some number theory, namely the Chinese remainder theorem.
0 references
cycle
0 references
path
0 references
road coloring problem
0 references
synchronizing coloring
0 references