On the Road Coloring Problem

DOI10.2307/2047767zbMath0745.05031OpenAlexW4251731194MaRDI QIDQ3970256

Joel Friedman

Publication date: 25 June 1992

Full work available at URL: https://doi.org/10.2307/2047767

zbMATH Keywords

road coloring problemred-blue coloringcollapsible coloring

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (14)

Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach ⋮ A vector space approach to the road coloring problem ⋮ An algorithm for road coloring ⋮ Synchronizing finite automata on Eulerian digraphs. ⋮ The generalized road coloring problem and periodic digraphs ⋮ A quadratic algorithm for road coloring ⋮ Cycles of relatively prime length and the road coloring problem ⋮ A note on the rank of semigroups. ⋮ The road coloring problem ⋮ Random walk in a finite directed graph subject to a road coloring ⋮ Synchronization problems in automata without non-trivial cycles ⋮ Modifying the Upper Bound on the Length of Minimal Synchronizing Word ⋮ Realization of an Ergodic Markov Chain as a Random Walk Subject to a Synchronizing Road Coloring ⋮ Černý's conjecture and the road colouring problem

Cites Work

• The road-colouring problem
• Equivalence of topological Markov shifts
• Endomorphisms and automorphisms of the shift dynamical system
• Similarity of automorphisms of the torus

This page was built for publication: On the Road Coloring Problem