Abstract (Michael Stiebitz)
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.
Last modified: September 19, 1997.
Kim Skak Larsen
(kslarsen@imada.sdu.dk)