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)
