학술논문
A semigroup approach to the road coloring problem.
Document Type
Proceedings Paper
Author
Budzban, Greg (1-SIL) AMS Author Profile; Mukherjea, Arunava (1-SFL) AMS Author Profile
Source
Subject
05 Combinatorics -- 05C Graph theory
05C20Directed graphs
20Group theory and generalizations -- 20M Semigroups
20M30Representation of semigroups; actions of semigroups on sets
05C20
20
20M30
Language
English
Abstract
The paper concerns the road colouring problem, from the theory of directed graphs. A strongly connected directed graph is given. Its vertices may be considered as buildings of a town and it may be supposed that in each building there is a person. The authors look for conditions for the existence of an edge coloring with the property that the same set of instructions allows each person to get to the same buildings. The problem is converted to one in semigroup theory. The existence of so-called semigroups with synchronizing instructions is investigated. A lot of results concerning this are presented.