Here's an example of a graph invariant which relates local estimates of some parameter with the global (or true) value of the parameter. The imperfection ratio of a graph $G$, denoted $imp(G)$, is defined to be $\sup_{x \ne 0} \frac{\chi_f(G,x)}{\omega(G,x)}$, where the supremum is taken over all nonzero rational vectors $x$, and $\chi_f(G,x)$ and $\omega(G,x)$ denote the fractional chromatic number and clique number, respectively, of the vertex-weighted graph $(G,x)$.

Consider a wireless communication network, where each node $v \in V(G)$ has a demand to transmit data for a fraction $x_v$ of each unit of time. Nodes which are adjacent in $G$ cannot transmit simultaneously due to wireless interference (this is how the edge set of $G$ is defined). The question is: can a demand vector $x = (x_v: v \in V(G))$ be satisfied? The demand vector $x$ is feasible if and only if $\chi_f(G,x) \le 1$. Computing $\chi_f(G,x)$ is NP-hard in general.

Am efficient, distributed mechanism for determining feasibility is to check whether the sum of the demands of each clique in $G$ is at most $1$. For a particular demand $x$, an optimal centralized algorithm would compute the numerator $\chi_f(G,x)$ of the definition of imperfection ratio. The distributed algorithm computes the denominator $\omega(G,x)$. Their ratio is the factor by which the distributed algorithm is away from optimal. The maximum possible value of this ratio, over all demand patterns, is the worst-case performance of this distributed algorithm, and is equal to the imperfection ratio of $G$.

The imperfection ratio was investigated by Gerke and McDiarmid, and applications of imperfection ratio to wireless networks has been studied here, here, and here.