Pseudoachromatic and connected-pseudoachromatic indices of the complete graph

A complete $k$-coloring of a graph $G$ is a (not necessarily proper) $k$-coloring of the vertices of $G$, such that each pair of different colors appears in an edge. A complete $k$-coloring is also called connected, if each color class induces a connected subgraph of $G$. The pseudoachromatic index of a graph $G$, denoted by ${\psi }^{\mathrm{\prime }}(G)$, is the largest $k$ for which the line graph of $G$ has a complete $k$-coloring. Analogously the connected-pseudoachromatic index of $G$, denoted by ${\psi }_c^{\mathrm{\prime }}(G)$, is the largest $k$ for which the line graph of $G$ has a connected and complete $k$-coloring. In this paper we study these two parameters for the complete graph $K_n$. Our main contribution is to improve the linear lower bound for the connected pseudoachromatic index given by Abrams and Berman [Australas J Combin 60 (2014), 314–324] and provide an upper bound. These two bounds prove that for any integer $n\ge 8$ the order of ${\psi }_c^{\mathrm{\prime }}(K_n)$ is $n^{3\mathrm{/}2}$. Related to the pseudoachromatic index we prove that for $q$ a power of $2$ and $n=q^2+q+1$, ${\psi }^{\mathrm{\prime }}(K_n)$ is at least $q^3+2q-3$ which improves the bound $q^3+q$ given by Araujo, Montellano and Strausz [J Graph Theory 66 (2011), 89–97].