On upper bounds for the pseudo-achromatic index

Abstract

In this paper, we give another approach to the pseudo-achromatic index and the achromatic index of a graph and study upper bounds for them. We have obtained the following best possible upper bounds: (i) Psi'(G)less than or equal to Psi(S)'(G)less than or equal to right perpendicular(e(G) + chi'(G))/2left perpendicular; and (ii) Psi'(G)less than or equal to Psi(S)'(G) less than or equal to max(1 less than or equal to k less than or equal to right perpendicularp/2left perpendicular) min{right perpendicularp Delta(G)/2kright perpendicular,2k(Delta(G)-1) + 1}. Using these bounds, the pseudo-achromatic indices of graphs of certain types are obtained which generalize the results of Bouchet (1978), Chiang and Fu (1995), Geller and Kronk (1974) and Jamison (1989) for achromatic indices to pseudo-achromatic indices.