The generalized road coloring problem and periodic digraphs

DOI10.1007/s00200-010-0135-zzbMath1242.05107arXiv0903.0192OpenAlexW2053812281MaRDI QIDQ429736

J. Herrera, H. S. Yoon, Philip Feinsilver, Greg Budzban

Publication date: 20 June 2012

Published in: Applicable Algebra in Engineering, Communication and Computing, Semigroup Forum (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0903.0192

zbMATH Keywords

Lie algebrastransformation semigroupsperiodic digraphsright groupsedge-coloring of digraphsLie-solvable semigroupssemigroups generated by matrices

Mathematics Subject Classification ID

Combinatorics on words (68R15) Semigroups of transformations, relations, partitions, etc. (20M20) Coloring of graphs and hypergraphs (05C15) Solvable, nilpotent (super)algebras (17B30) Directed graphs (digraphs), tournaments (05C20)

Related Items

A vector space approach to the road coloring problem, The road problem and homomorphisms of directed graphs, The generalized road coloring problem and periodic digraphs, A quadratic algorithm for road coloring, Random walk in a finite directed graph subject to a road coloring, Realization of an Ergodic Markov Chain as a Random Walk Subject to a Synchronizing Road Coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The generalized road coloring problem and periodic digraphs
• Semigroups and the generalized road coloring problem
• The road coloring problem
• A vector space approach to the road coloring problem
• Synchronizing finite automata on Eulerian digraphs.
• Zeon Algebra, Fock Space, and Markov Chains
• On the Road Coloring Problem
• Remarks on the kernel of a matrix semigroup