2
$\begingroup$

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.


Edit: With "general" I mean: considering in a systematic way different "natural" and "important"coloring functions (not all of them at once), studying their properties and relating them in insightful ways.

(Compare this to general graph theory: The general graph is just a function $V\times V \rightarrow \{0,1\}$ and at that level of generality one might doubt that there's much of a theory. But there is.)

  • 1
    Where do the context-free grammars enter into it?2012-07-05
  • 0
    Via the grammatical roles (= colors) the grammatical constituents (= symbols of the alphabet) do play.2012-07-05
  • 0
    Any hint for downvoting is welcome.2012-07-05
  • 0
    It wasn't me. ${}{}$2012-07-05
  • 0
    Didn't want to blame anyone.2012-07-05
  • 0
    I don't know if this is remotely close to what you're looking for but I remember this book has some graph logic in it: http://books.google.com/books/about/The_Strange_Logic_of_Random_Graphs.html?id=u2c3LpjWs7EC&redir_esc=y2012-07-05
  • 2
    A coloring is a function from the vertices of a (finite) graph to an initial segment of the natural numbers. A coloring rule is a subset of the set of all such functions. At that level of generality, I doubt there's much of a theory.2012-07-06

0 Answers 0