19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
On the pseudoachromatic and achromatic index of the complete graph
Presented by Mr. Christian RUBIO-MONTIEL
Type: Oral presentation
Track: General session
Content
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.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Co-authors
- Dr. J. José MONTELLANO-BALLESTEROS Instituto de Matematicas, UNAM, Mexico
- Dr. Ricardo STRAUSZ Instituto de Matematicas, UNAM, Mexico
- Dr. M. Gabriela ARAUJO-PARDO Instituto de Matematicas, UNAM, Mexico