The generalized road coloring problem and periodic digraphs

DOI10.1007/S00200-010-0135-ZzbMATH Open1242.05107arXiv0903.0192OpenAlexW2053812281MaRDI QIDQ429736FDOQ429736

Authors: Ph. Feinsilver, G. Budzban 

Publication date: 20 June 2012

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

Abstract: A proof of the Generalized Road Coloring Problem, independent of the recent work by Beal and Perrin, is presented, using both semigroup methods and Trakhtman's algorithm. Algebraic properties of periodic, strongly connected digraphs are studied in the semigroup context. An algebraic condition which characterizes periodic, strongly connected digraphs is determined in the context of periodic Markov chains.

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

Recommendations

• Semigroups and the generalized road coloring problem
• The generalized road coloring problem and periodic digraphs
• scientific article; zbMATH DE number 1551726
• A vector space approach to the road coloring problem
• Completely simple semigroups of matrices

zbMATH Keywords

transformation semigroupsLie algebrasedge-coloring of digraphsLie-solvable semigroupsperiodic digraphsright groupssemigroups generated by matrices

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Synchronizing finite automata on Eulerian digraphs.
• The road coloring problem
• Zeon algebra, Fock space, and Markov chains
• On the Road Coloring Problem
• Title not available (Why is that?)
• The generalized road coloring problem and periodic digraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Remarks on the kernel of a matrix semigroup
• Semigroups and the generalized road coloring problem
• A vector space approach to the road coloring problem

Cited In (10)

• Title not available (Why is that?)
• The generalized road coloring problem and periodic digraphs
• Semigroups and the generalized road coloring problem
• A vector space approach to the road coloring problem
• The road problem and homomorphisms of directed graphs
• Random walk in a finite directed graph subject to a road coloring
• A min-max theorem about the road coloring conjecture
• A note on the road-coloring conjecture
• Realization of an ergodic Markov chain as a random walk subject to a synchronizing road coloring
• A quadratic algorithm for road coloring

This page was built for publication: The generalized road coloring problem and periodic digraphs

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