Mariusz WOŹNIAK

(WMS)

O dowolnych podziałach grafów

Problem dowolnego podziału grafu można przedstawić następująco:

Przypuśćmy, że mamy graf $G$ rzędu n.

Pytanie: czy mając p liczb $n_1$, $n_2$ ,..., $n_p$, takich, że ich suma wynosi n możemy tak podzielić wierzchołki grafu $G$, aby dostać $p$ podgrafów mających odpowiednio $n_1$, $n_2$ etc. wierzchołków tak, aby każdy z nich był spójny?

Jeśli jest to możliwe dla dowolnego ciągu liczb naturalnych, których suma wynosi n to graf $G$ nazywamy dowolnie podzielnym (DP).

Referat poświęcony jest przypomnieniu znanych faktów oraz kilku mocniejszym wersjom tego problemu.

Serdecznie zapraszamy wszystkich chętnych!