> here are only three nontrivial complexity levels (2, 3, 4) The four colour limit is only for planar graphs. Dependency graphs need not be planar. Also ther

> here are only three nontrivial complexity levels (2, 3, 4) The four colour limit is only for planar graphs. Dependency graphs need not be planar. Also there is a very well understood connection between software complexity and graph colourings: register allocation. If you model variables as vertices, and place edges between variables that are required at the same time, then assigning locations to variables is a graph colouring. I think this might generalise: the number of graph colours tells you something about the maximum number of things you need to keep track of simultaneously in order to deal with one locality in the graph.