DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE ODENSE UNIVERSITY Decomposition of Graphs and Digraphs Michael Stiebitz Mathematisches Institut Technische Universitaet Ilmenau Tuesday, September 23, 1997, at 2:15 PM The Seminar Room In the talk we shall consider questions of the type: Let p be a parameter for a graph or digraph and let s,t >= 1 be integers. Does there exist a smallest number p(s,t) such that the vertex set of any graph or digraph G with p(G) >= p(s,t) has a partition (A,B) satisfying p(G(A)) >= s and p(G(B)) >= t where G(X) denotes the subgraph or subdigraph of G induced by X? We discuss this question for several parameters like maximum degree, minimum degree, connectivity or chromatic number and give a survey of some results and open problems. Bjarne Toft