A note on the Erdös-Faber-Lovász Conjecture: quasigroups and complete digraphs

Abstract

A decomposition of a simple graph $G$ is a pair $(G,P)$ where $P$ is a set of subgraphs of $G$, which partitions the edges of $G$ in the sense that every edge of $G$ belongs to exactly one subgraph in $P$. If the elements of $P$ are induced subgraphs then the decomposition is denoted by $[G,P]$. A $k$-$P$-coloring of a decomposition $(G,P)$ is a surjective function that assigns to the edges of $G$ a color from a $k$-set of colors, such that all edges of $H\in P$ have the same color, and, if $H_1,H_2\in P$ with $V(H_1)\cap V(H_2)\ne \varnothing$ then $E(H_1)$ and $E(H_2)$ have different colors. The \emph{chromatic index} ${\chi }^{\prime }((G,P))$ of a decomposition $(G,P)$ is the smallest number $k$ for which there exists a $k$-$P$-coloring of $(G,P)$. The well-known Erdös-Faber-Lovász Conjecture states that any decomposition $[K_n,P]$ satisfies ${\chi }^{\prime }([K_n,P])\le n$. We use quasigroups and complete digraphs to give a new family of decompositions that satisfy the conjecture.

arXiv comment4 pages, 1 figure

References in corpus (1)

• A note on Erdös-Faber-Lovász Conjecture and edge coloring of complete graphs