We study the descriptive complexity of parity games by taking into
account the coloring of their game graphs whilst ignoring their owner-
ship structure. Di erent colorings of the same graph are identi ed if
they determine the same winning regions and strategies, for all ownership
structures of nodes. The Rabin index of a parity game is the minimum of
the maximal color taken over all equivalent coloring functions. We show
that deciding whether the Rabin index is at least k is in P for k = 1
but NP-hard for all xed k 2. We present an EXPTIME algorithm
that computes the Rabin index by simplifying its input coloring function.
When replacing simple cycle with cycle detection in that algorithm, its
output over-approximates the Rabin index in polynomial time. Experi-
mental results show that this approximation yields good values in practice.