Stavros Kousidis
Zentrum für Angewandte Informatik Köln
Universität zu Köln

Färbung von gemischten Hypergraphen nach Vitaly I. Voloshin

Gemischte Hypergraphen und deren Färbung wurden von Vitaly I. Voloshin 1992 eingeführt. Ich möchte einen kleinen Überblick über das Konzept und dessen Anwendungen geben aber vor allem auf erste Strukturen hinweisen, die bei klassischer Graphenfärbung nicht auftauchen. Genauer, nach Einführung der grundlegenden Begriffe werden wir auf nichtfärbbare gemischte Hypergraphen stoßen und als einen Typ von nichtfärbbaren gemischten Hypergraphen werde ich „vollständige (l,m)-uniformen gemischten Hypergraphen“ erläutern. Weiterhin wird das chromatische Spektrum behandelt und Lücken in diesem Spektrum werden diskutiert. Insbesondere werde ich auf diese Lücken vor dem Hintergrund der uniformen, intervall und planaren gemischten Hypergraphen eingehen.

Wer einen ersten Blick riskieren möchte, kann folgende (gut gepflegte) Webseite besuchen:
http://spectrum.troy.edu/~voloshin/mh.html

Literatur:

[1]

Vitaly I. Voloshin. Coloring Mixed Hypergraphs: Some Results and Open Problems. Rendiconti del Seminario Matematico di Messina. Serie II, Tomo XXV, Volume n.9 (2003), pages 237-244. Proceedings of the International Symposium on Graphs, Designs and Applications. Villa Pace, Messina, 30 September - 4 October, 2003

[2]

Vitaly I. Voloshin. Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. AMS, Providence RI, 2002. Fields Institute Monographs, Vol. 17.

[3]

T. Jiang, D. Mubayi, Zs. Tuza, V. Voloshin, D. West. The Chromatic Spectrum of Mixed Hypergraphs. Graphs and Combinatorics, 18 (2002) 309-318.