On a Conjecture for a Hypergraph Edge Coloring Problem

Abstract

Let $H=(\mathcal{M}\cup \mathcal{J},E\cup \mathcal{E})$ be a hypergraph with two hypervertices ${\mathcal{G}}_1$ and ${\mathcal{G}}_2$ where $\mathcal{M}={\mathcal{G}}_1\cup {\mathcal{G}}_2$ and ${\mathcal{G}}_1\cap {\mathcal{G}}_2=\varnothing$. An edge $\{h,j\}\in E$ in a bi-partite multigraph graph $(\mathcal{M}\cup \mathcal{J},E)$ has an integer multiplicity $b_{jh}$, and a hyperedge $\{{\mathcal{G}}_{\ell },j\}\in \mathcal{E}$, $\ell =1,2$, has an integer multiplicity $a_{j\ell }$. It has been conjectured in [5] that $\chi \prime (H)=\lceil \chi {\prime }_f(H)\rceil$, where $\chi \prime (H)$ and $\chi {\prime }_f(H)$ are the edge chromatic number of $H$ and the fractional edge chromatic number of $H$ respectively. Motivation to study this hyperedge coloring conjecture comes from the University timetabling, and open shop scheduling with multiprocessors. We prove this conjecture in this paper.