Back to Seminars
home page

Institutt for informatikk seminar: Thursday 7 feb, kl. 14:15

Coloring hypergraphs

Prof Jan Kratochvil

Dept Applied Mathematics, Charles University, Prague

We give a commented survey of recent results on coloring hypergraphs, with emphasis on clique hypergraphs of graphs, face hypergraphs of embedded graphs and mixed hypergraphs. The results will include both algorithmic and complexity results on deciding the existence of a coloring by limited number of colors, and existence theorems. A hypergraph is a collection of subsets (refered to as hyperedges) of the vertex set. A vertex coloring is proper if no hyperedge is monochromatic. Hyperedges of the clique hypergraph of a graph are its maximal cliques, hyperedges of the face hypergraph of an embedded graph are its faces. Face hypergraphs of plane graphs are of special interest. Mixed hypergraphs are hypergraphs with two types of edges, so called C-edges and D-edges. For a coloring to be proper, we require that no D-edge be monochromatic while no C-edge be totally multicolored. In this setting the maximum number of colors that can be used in a proper coloring is not easy to determine. Several open problems will be presented.

Back to seminar homepage