On the Road Coloring Problem

DOI10.2307/2047767MaRDI QIDQ3970256zbMATH OpenOpenAlexFDO

Authors Joel Friedman

Publication date 25 June 1992

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

zbMATH Keywords

collapsible coloringred-blue coloringroad coloring problem

Mathematics Subject Classification ID

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

Recommendations

• A vector space approach to the road coloring problem
• A note on the road-coloring conjecture
• Cycles of relatively prime length and the road coloring problem
• A quadratic algorithm for road coloring
• A min-max theorem about the road coloring conjecture

Cites work

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

Cited in

(15)

• Synchronizing finite automata on Eulerian digraphs.
• An algorithm for road coloring
• Černý's conjecture and the road colouring problem
• A quadratic algorithm for road coloring
• A note on the road-coloring conjecture
• 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
• A min-max theorem about the road coloring conjecture
• Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach
• Cycles of relatively prime length and the road coloring problem
• A note on the rank of semigroups.
• Efficiently computing the minimum rank of a matrix in a monoid of zero-one matrices
• The road coloring problem
• Random walk in a finite directed graph subject to a road coloring
• A vector space approach to the road coloring problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3970256)