Semigroups and the generalized road coloring problem
type: Item
instance of: scholarly article
title: Semigroups and the generalized road coloring problem
zbMATH Open document ID: 1057.05031
author: Greg Budzban
published in: Semigroup Forum
publication date: 2005-02-16T00:00:00Z
review text: Consider a finite automaton having a finite set \(X\) of states, a finite set of inputs \({\mathcal A}\) and a state transition function \(\delta \). The semigroup \(S\) generated under composition by \(\{R_{a}:a\in {\mathcal A}\}\) is called the semigroup of the automaton, where \(R_{a}(x)=\delta (x,a)\). For any digraph \(G=(V,E)\) such that all vertices have the same outdegree, any labeling of the edges with members of \({\mathcal A}\) such that all the edges issuing from any given vertex have distinct labelings is called a coloring of the digraph. Any coloring uniquely determines an automaton, where \(R_{a}(x)=xa\) is the terminal point of the directed edge with initial point \(x\) and label \(a\) and we refer to the semigroup \(S\) as the coloring semigroup. The main result of this paper is the following: Let \(G\) be a strongly connected digraph such that all vertices have the same outdegree and \(S=\{R_{a}:a\in {\mathcal A}\}\) be a minimal coloring semigroup with kernel \(K\). If \(K\) is a right group with rank(\(K)=t\), then \(G\) is periodic of order \(t\).
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 20M20
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 2134642
zbMATH Keywords: digraph
zbMATH Keywords: coloring semigroups
zbMATH Keywords: completely simple semigroups
MaRDI profile type: Publication
full work available at URL: s00233-004-0129-x
OpenAlex ID: W2077263939
DOI: 10.1007/S00233-004-0129-X
Recommended article: Q4523963
Recommended article: The generalized road coloring problem and periodic digraphs
Recommended article: Q3173860
Recommended article: Q3698833
Recommended article: Hindman's coloring theorem in arbitrary semigroups
Recommended article: The Schur-Erdős problem for semi-algebraic colorings
Recommended article: A note on the road-coloring conjecture
Recommended article: Q3331430
Recommended article: Coloring the power graph of a semigroup
description: scientific article; zbMATH DE number 2134642