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.

Back to all abstracts