Skip to main content
1 of 2
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

Local-Global approach to graph theory

This question is inspired from

(i) Theorems like the "universal friend theorem": If every two vertices in a connected graph $G$ share a unique common neighbor, then there is a vertex connected to all the others in $G$.

and (ii) Results like: If the subgraph spanned by every $k$ vertices in $G$ is $2$-colorable, then $\chi(G)=O(n^{O(1/k)})$.

Unfortunately I don't know many results similar in flavor to the above, therefore the question. What are some important theorems/principles/methods in graph theory that help us determine global parameters of the graph from local data? (I am being intentionally vague about what I mean by "local", examples could vary from data on subgraphs spanned by few vertices, to data on subgraphs spanned by vertices at small distance from a base vertex)

Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402