  Let G be a finite graph with the non-k-order property (essentially, a uniform
finite bound on the size of an induced sub-half-graph). A major result of the
paper applies model-theoretic arguments to obtain a stronger version of
Szemer\'edi's regularity lemma for such graphs, Theorem 5.18, in which there
are no irregular pairs, the bounds are significantly improved, and each
component satisfies an indivisibility condition. Motivation for this work comes
from a coincidence of model-theoretic and graph-theoretic ideas. Namely, it was
known that the "irregular pairs" in the statement of Szemer\'edi's regularity
lemma cannot be eliminated, due to the counterexample of half-graphs. The
results of this paper show in what sense this counterexample is the only
essential difficulty. The proof is largely model-theoretic (though written to
be accessible to finite combinatorialists): arbitrarily large half-graphs
coincide with model-theoretic instability, so in their absence, structure
theorems and technology from stability theory apply. In addition to the theorem
quoted, we give several other regularity lemmas with different advantages, in
which the indivisibility condition on the components is improved (at the
expense of letting the number of components grow with |G|) and extend some of
these results to the larger class of graphs without the independence property.
