19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

On the pseudoachromatic and achromatic index of the complete graph

Presented by Mr. Christian RUBIO-MONTIEL
Type: Oral presentation
Track: General session


Let $G$ a simple graph. A colouring of its vertices $\varsigma:V\rightarrow\{1,...,k\}$ is called \emph{complete} if each pair of different colours appears in a edge. The \emph{pseudoachromatic number} $\psi(G)$ is the maximum $k$ for which there exist a complete colouring of $G$. If the colouring is required also to be proper (i. e., that each chromatic class is independent), then such a maximum is know as the \emph{achromatic number} and it will be denoted here by $\alpha(G)$. We are mainly interested in the pseudoachromatic number $\psi(n):=\psi(L(K_{n}))$ of the complete graph's line graph -also know as the \emph{pseudoachromatic index} of the complete graph- and its relation with the \emph{achromatic index} $\alpha(n):=\alpha(L(K_{n}))$. In this talk, we expose the principal motivation of this research, a deep result due to Bouchet in 1978: Let $q$ be and odd natural number, and let $m=p^{2}+p+1$. A projective plane $\Pi_{p}$ of order $p$ exists if and only if $\alpha(m)=pm$. Also, we expose our work made in this direction:\\ In a recently paper, my coauthors proved that $\psi(n)=q(n+1)$ when $n=q^{2}+2q+2$ and $q=2^{\gamma}$ for $\gamma\in\mathbb{N}$ using also the properties of the projective planes. Now, we have shown that $\psi(n-a)=\alpha(n-a)=q(n-2a)$ when $n=(q+1)^{2}$, $q=2^{\gamma}$ for $\gamma\geq2$ and $a\in\{0,1,2\}$ using also projective planes.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors