the wikipedia article shows an easy construction for an even n with n-1 colors.

A picture showing the solution for K8 is given too.

Basically, if you have a regular n-1 polygon plus it's center and connect all the nodes you'll have a Kn graph. Because of the regularity this graph has n-1 groups of (n-2)/2 parallel edges plus one perpendicular from the center m to the missing node. Parallel edges can never be adjacent.

I tried to sketch it for K6 with a pentagram a b c d e and a center m

            d
            |
       e---------c
            m

         a-----b
[download]

Of course it's hard to draw a regular pentagram in ASCI graphic, the display will also depend on your browser settings.

But I hope it's obvious that symmetry leads to a solution with 5 colors here, which can be generalized to n even.