We study the k-improper chromatic number of graphs that are obtained as
follows.
We pick points X_1, ..., X_n from the plane at random (i.i.d. according to
some probability distribution) and we
join X_i, X_j by an edge if d(X_i, X_j) < r for some r > 0.
We are interested in the behaviour of these graphs as n tends to infinity,
where it is assumed that
r = r(n) tends to 0 as n tends to infinity.
Results by McDiarmid (2003), Penrose (2003) and McDiarmid and Müller
(2005) on
the chromatic number of these graphs partially extend to the k-improper
chromatic number with some important
differences.
This is joint work with J.-S. Sereni and R.J.Kang.