On upper bounds for the pseudo-achromatic index (Q1377748)

Let \(\Psi'(G)\) and \(\Psi'_S(G)\) denote the achromatic index and the pseudo-achromatic index of \(G\), respectively. In this paper it is proved that (i) \(\Psi'(G)\leq\Psi'_S(G)\leq\lfloor(e+\chi'(G))/2\rfloor\), and (ii) \(\Psi'(G)\leq\Psi'_S(G)\leq\max_{1\leq k\leq\lfloor p/2\rfloor}\min({\lfloor p\Delta/2k\rfloor,2k(\Delta-1)+1})\), where \(p\), \(e\), \(\Delta\) and \(\chi'(G)\) denote the order, size, maximum degree and chromatic index of \(G\), respectively. Using these bounds, the pseudo-achromatic indices of graphs of certain types (e.g. paths, cycles, complete graphs or complete multipartite graphs) are obtained which generalize the results of \textit{A. Bouchet} [Cah. Cent. Etud. Rech. Oper. 20, 331-340 (1978; Zbl 0404.05026)], \textit{N.-P. Chiang} and \textit{H.-L. Fu} [Discrete Math. 141, 61-66 (1995; Zbl 0827.05026)], \textit{D. Geller} and \textit{H. Kronk} [Fundamenta Math. 85, 285-290 (1974; Zbl 0287.05119)] and \textit{R. E. Jamison} [Discrete Math. 74, No. 1/2, 99-115 (1989; Zbl 0667.05024)] for achromatic indices to pseudo-achromatic indices.