RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.8, n.1 (22), 2000/

Integer programming models for colorings of mixed hypergraphs

Authors: Lozovanu Dmitrii, Vitaly Voloshin

Abstract

A mixed hypergraph H=(X,C,D) consists of the vertex set X and two families of subsets: the family C of C-edges and the family D of D-edges. In a coloring, every C-edge has at least two vertices of common color, while every D-edge has at least two vertices of different colors. The largest (smallest) number of colors for which a coloring of a mixed hypergraph H using all the colors exists is called the upper (lower) chromatic number and is denoted not(X)(H) (X(H)). We consider integer programming models for colorings of mixed hypergraphs in order to show that algorithms for optimal colorings may be transformed and used for finding optimal solutions of the respective integer programming problems.

D.Lozovanu, V.Voloshin,
Institute of Mathematics
and Computer Science,
Academy of Sciences of Moldova
5, Academiei str., Kishinev,
MD2028, Moldova
phone: 73-35-83
e-mail: ,

Fulltext

Adobe PDF document0.15 Mb