Graph Labelings and Continuous Factors of Dynamical Systems

Abstract

A labeling of a graph is a function from the vertex set of the graph to some finite set.  Certain dynamical systems (such as topological Markov shifts) can be defined by directed graphs.  In these instances, a labeling of the graph defines a continuous, shift-commuting factor of the dynamical system.  We find sufficient conditions on the labeling to imply classification results for the factor dynamical system.  We define the topological entropy of a (directed or undirected) graph and its labelings in a way that is analogous to the definition of topological entropy for a shift space in symbolic dynamics.  We show, for example, if $G$ is a perfect graph, all proper $\chi(G)$-colorings of $G$ have the same entropy, where $\chi(G)$ is the chromatic number of $G$.