Pseudoachromatic and connected-pseudoachromatic indices of the complete graph
Gabriela Araujo Pardo
Mathematics Institute, National University of Mexico
Christian Rubio
Mathematics Institute, National University of Mexico
PDF
Minisymposium: FINITE GEOMETRY
Content: In this paper we study these two parameters for the complete graph $K_n$. First, we prove that, when $q$ is a power of $2$ and $n=q^2+q+1$, the pseudoachromatic index $\psi'(K_n)$ of the complete graph $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]. 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\geq 8$ the order of $\psi_c'(K_n)$ is $n^{3/2}.$ {\bf{Remark:}} The colorations that induce the lower bounds are given using the structure of Projectives Planes.