On a Conjecture for a Hypergraph Edge Coloring Problem

arXiv2006.06393MaRDI QIDQ6342632

Publication date: 11 June 2020

Abstract: Let

H = (m a t h c a l M c u p m a t h c a l J, E c u p m a t h c a l E)

be a hypergraph with two hypervertices

m a t h c a l G_{1}

and

m a t h c a l G_{2}

where

m a t h c a l M = m a t h c a l G_{1} c u p m a t h c a l G_{2}

and

m a t h c a l G_{1} c a p m a t h c a l G_{2} = v a r n o t h i n g

. An edge

h, j i n E

in a bi-partite multigraph graph

(m a t h c a l M c u p m a t h c a l J, E)

has an integer multiplicity

b_{j h}

, and a hyperedge

m a t h c a l G_{e l l}, j i n m a t h c a l E

,

e l l = 1, 2

, has an integer multiplicity

a_{j e l l}

. It has been conjectured in [5] that

c h i p r i m e (H) = l c e i l c h i p r i m e_{f} (H) c e i l

, where

c h i p r i m e (H)

and

c h i p r i m e_{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.

This page was built for publication: On a Conjecture for a Hypergraph Edge Coloring Problem