Colorings and interpretations: a connection between graphs and grammar forms

AbstractA mechanism for constructing families of “similar” graphs is introduced. This mechanism is essentially identical to the one considered in the theory of grammar forms and, at the same time, generalizes the notion of coloring of graphs. The mechanism applies to both directed and undirected graphs. The paper investigate hierarchies of families of graphs obtained by this mechanism, both in the directed and undirected case