MULTIPARTITE TOURNAMENTS:

Results, problems, and conjectures

Lutz Volkmann

Lehrstuhl II für Mathematik, RWTH Aachen, 52056 Aachen, Germany e-mail: volkm@math2.rwth-aachen.de

A tournament is an orientation of a complete graph, and in general a multipartite tournament is an orientation of a complete n-partite graph. Many interesting results about cycles and paths in tournaments are known, but closely related problems involving cycles and paths in multipartite tournaments have received little attention until recently. We describe some of the rapid progress in recent years on this topic, including open problems and conjectures.

References

[1] J. Bang-Jensen and G. Gutin, Generalizations of tournaments: a survey, J. Graph Theory, 28 (1998), 171-202.

[2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer-London (2000).

[3] Y. Guo, Semicomplete Multipartite Digraphs: a Generalization of Tournaments, Habilitation thesis, RWTH Aachen, Germany (1998), 102 p.

[4] G. Gutin, Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey, J. Graph Theory 19 (1995), 481-505.

[5] M. Tewes, In-tournaments and semicomplete multipartite digraphs, Ph. D. thesis, RWTH Aachen, Germany, Aachener Beiträge zur Mathematik 25 (1999), 114 p.

[6] L. Volkmann, Cycles in multipartite tournaments: Results and problems, Discrete Math., to appear.

[7] A. Yeo, Semicomplete Multipartite Digraphs, Ph. D. thesis, Odense University, Denmark (1998).