In Ben Steven's article Colored graphs and their properties I read:
We "color" a graph by assigning various colors to the vertices of that graph. [...] this process of coloring is generally governed by a set of coloring rules. For example, the most basic set of coloring rules, referred to as regular coloring, consists of a single rule: no two adjacent vertices may have the same color.
What I am looking for is a truly general theory of graph colorings and resp. general coloring rules.
The theory should be so general to include symmetric (= orderless) context-free grammars.