Christian RUBIO ( UNAM, Mexiko ): Geometric achromatic and pseudochromatic index

Abstract

Let $G$ be a simple graph. A (vertex) coloring of $G$ is proper if no two adjacent vertices have the same color. Moreover if each pair of colors appears on at least one pair of adjacent vertices, then the coloring is complete. The biggest number $k$ for which a complete coloring of (the vertices of) $G$ exist is the pseudoachromatic number $\psi(G)$ of $G$. The biggest number $k$ for which a complete and proper coloring of (the vertices of) $G$ exist is the achromatic number $\alpha(G)$ of $G$. Clearly we have that $$\chi(G) \leq \alpha(G) \leq \psi(G)$$ where $\chi(G)$ denotes, as usual, the chromatic number of $G$. The pseudoachromatic index $\psi_1(G)$ of $G$ is defined as the pseudoachromatic number of the line graph $L(G)$ of $G$. The achromatic index $\alpha_1(G)$ of $G$ is defined as the achromatic number of the line graph of $G$. Notationally, $\psi_1(G) = \psi(L(G))$ and $\alpha_1(G) = \alpha(L(G))$. Bouchet in 1978 proved that if $q$ is an odd number and $n=q^2 + q + 1$, the projective plane of order $q$ exist if and only if $\alpha_1(K_n) = qn$. This result has motivated the study of the achromatic and pseudoachromatic indices in complete graphs. In this paper we extend the notion of pseudoachromatic and achromatic index to geometric graphs and we define the geometric achromatic and pseudoachromatic index for a graph $G$. Particularly, we present upper and lower bounds for the achromatic and pseudoachromatic indices of complete geometric graphs.