On the pseudoachromatic index of the complete graph
Gabriela Araujo‐Pardo, Juan José Montellano‐Ballesteros, Ricardo Strausz · Journal of Graph Theory · 2010
Let q = 2β be, for some β∈ℕ, and let n = q2 + q+ 1. By exhibiting a complete coloring of the edges of Kn, we show that the pseudoachromatic number ψ(Gn) of the complete line graph Gn = L(Kn)—or the pseudoachromatic index of Kn, if you will—is at least q3 + q. This bound improves the implicit bound of Jamison [Discrete Math 74 (1989), 99–115] which is given in terms of the achromatic number: ψ(Gn)≥α(Gn)≥q3 + 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