Local-global approach to graph theory

There is a very nice survey Local-global phenomena in graphs by N. Linial


A nice result giving a negative answer towards your question is due to Erdos (1962, found in Alon and Spencer amongst other places).

It says that for all k there exists $\epsilon>0$ so that for all sufficiently large n there exist graphs on n vertices with chromatic number greater than k, $\chi(G)>k$, but for every subgraph S induced by at most $\epsilon n$ vertices, $\chi(S)\leq 3$.

In other words, not much information can be deduced about the chromatic number of graphs from the chromatic number of their subgraphs (in general) - except for results such as the one you mentioned. So local behaviour can be very different to global behaviour, at least as chromatic numbers go.


Does planarity qualify as a "local condition?" I'd think it should, but I don't see how to put it into the "data on small/local subgraphs" framework.

Anyway, if it does, you have of course the four-color theorem, and even better the five-color theorem, whose proofs essentially take advantage of the fact that we sort of understand how to move between "local" and "global" in topological spaces.

ETA: More generally, of course, there's the whole subfield of "structural graph theory" and its methods. I don't know that the graph minor theorem is "local-to-global" -- it's really more "local-to-a-different-kind-of-local" -- but it's probably the most important structural result.

Structural graph theory is something that I wish I knew about, but looks so horrifically technical and difficult that I'm sort of afraid to study it. There are clearly some deep patterns hidden there, though -- witness how Robertson, Seymour, and Thomas all worked on the proof of the Strong Perfect Graph Conjecture, which used a decomposition argument and had a hugely structural flavor despite being (as far as I can tell) mostly unrelated to the more topological work they'd previously done.

Tangentially, this recent preprint of Dvorak, Kral and Thomas caught my eye for exactly the "local properties" reason. Unfortunately the proof of the main theorem doesn't seem to be available yet...