학술논문
Semigroups and the Generalized Road Coloring Problem.
Document Type
Article
Author
Source
Subject
*DIRECTED graphs
*GRAPH coloring
*SEMIGROUPS (Algebra)
*GROUP theory
*GRAPH theory
*
*
*
*
Language
ISSN
0037-1912
Abstract
The road coloring problem has been open for some 25 years. This paper shows how algebraic methods, specifically semigroup theory, can be used to both generalize and shed light on the problem. Given a strongly connected digraph, the notion of a coloring semigroup is defined. The main result shows that the existence of a coloring semigroup whose kernel is a minimum rank right group of rank t implies the digraph is periodic of order t. [ABSTRACT FROM AUTHOR]