Semigroups and the generalized road coloring problem

DOI10.1007/S00233-004-0129-XMaRDI QIDQ706042zbMATH OpenOpenAlexFDO

Authors Greg Budzban

Publication date 16 February 2005

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00233-004-0129-x

zbMATH Keywords

coloring semigroupscompletely simple semigroupsdigraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Semigroups of transformations, relations, partitions, etc. (20M20) Semigroups in automata theory, linguistics, etc. (20M35)

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\).

Recommendations

• scientific article; zbMATH DE number 1551726
• Labeling semi group of an automaton and road coloring conjecture
• scientific article; zbMATH DE number 3922703
• Hindman's coloring theorem in arbitrary semigroups
• The Schur-Erdős problem for semi-algebraic colorings
• A note on the road-coloring conjecture
• scientific article; zbMATH DE number 3863485
• Coloring the power graph of a semigroup

Cited in

(5)

• Realization of an ergodic Markov chain as a random walk subject to a synchronizing road coloring
• Labeling semi group of an automaton and road coloring conjecture
• A note on the rank of semigroups.
• 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: Semigroups and the generalized road coloring problem

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