Premium
On the pseudoachromatic index of the complete graph
Author(s) -
AraujoPardo M. Gabriela,
MontellanoBallesteros, Juan José,
Strausz Ricardo
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20491
Subject(s) - mathematics , combinatorics , graph , upper and lower bounds , achromatic lens , discrete mathematics , edge coloring , line graph , graph power , physics , mathematical analysis , astronomy
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