16–18 May 2014
Rogla, Slovenia
UTC timezone

On achromatic and pseudoachromatic indices of affine spaces

Not scheduled
Rogla, Slovenia

Rogla, Slovenia

Speaker

Prof. Gyorgy Kiss (Eötvös Loránd University)

Description

A decomposition of a simple graph G=(V(G),E(G)) is a pair $[G,\mathcal{D}]$ where $\mathcal{D}$ is a set of induced subgraphs of $G$, such that every edge of $G$ belongs to exactly one subgraph in $\mathcal{D}$. A \emph{coloring} of a decomposition $[G,\mathcal{D}]$ with $k$ colors is a surjective function that assigns to edges of $G$ a color from a $k$-set of colors, such that all edges of $H\in \mathcal{D}$ have the same color. A coloring of $[G,\mathcal{D}]$ with $k$ colors is \emph{proper}, if for all $H_1,H_2\in\mathcal{D}$ with $H_1\not= H_2$ and $V(H_1)\cap V(H_2)\neq\emptyset$, then $E(H_1)$ and $E(H_2)$ have different colors. The \emph{chromatic index} $\chi'([G,\mathcal{D})]$ of a decomposition is the smallest number $k$ for which there exists a proper coloring of $[G,\mathcal{D}]$ with $k$ colors. A coloring of $[G,\mathcal{D}]$ with $k$ colors is \emph{complete} if each pair of colors appears on at least a vertex of $G$. The \emph{pseudoachromatic index} $\psi'([G,\mathcal{D}])$ of a decomposition is the largest number $k$ for which there exist a complete coloring with $k$ colors. The \emph{achromatic index} $\alpha'([G,\mathcal{D}])$ of a decomposition is the largest number $k$ for which there exist a proper and complete coloring with $k$ colors. If $\mathcal{D}=E(G)$ then $\chi'([G,E])$, $\alpha'([G,E])$ and $\psi'([G,E])$ are the usual \emph{chromatic}, \emph{achromatic} and \emph{pseudoachromatic indices} of $G$, respectively. Clearly we have that \[ \chi'([G,\mathcal{D}]) \leq \alpha'([G,\mathcal{D}]) \leq \psi'([G,\mathcal{D}]). \] Designs define decompositions of the corresponding complete graphs in the natural way. Identify the points of a $(v,\kappa)$-design $D=(\mathcal{V},\mathcal{B})$ with the set of vertices of the complete graph $K_v$. Then the set of points of each block of $D$ induces in $K_v$ a subgraph isomorphic to $K_{\kappa}$ and these subgraphs give a decomposition of $K_v.$ In this talk we consider the decomposition of $K_{q^n}$ coming from the line-set ${\mathcal L}$ of the finite affine space $\mathrm{AG}(n,q).$ We prove that $\psi' ([K_{q^2} , {\mathcal L} ])=\lfloor \tfrac{(q+1)^2}{2} \rfloor$ and we give give estimates on achromatic and pseudoachromatic indices of $[K_{q^n} , {\mathcal L} ]$ for $n>2.$

Primary author

Prof. Gyorgy Kiss (Eötvös Loránd University)

Presentation materials

There are no materials yet.