On the pseudoachromatic index of the complete graph

Let q = 2 β be, for some β∈ℕ, and let n = q 2 + q + 1. By exhibiting a complete coloring of the edges of K n , we show that the pseudoachromatic number ψ( G n ) of the complete line graph G n = L ( K n )—or the pseudoachromatic index of K n , if you will—is at least q 3 + q . This bound improves the implicit bound of Jamison [Discrete Math 74 (1989), 99–115] which is given in terms of the achromatic number: ψ( G n )≥α( G n )≥ q 3 + 1. We also calculate, precisely, the pseudoachromatic number when q + 1 extra points are added:Copyright © 2010 John Wiley Periodicals, Inc. J Graph Theory 66:89‐97, 2011