Mariusz WOŹNIAK

(WMS)

O pewnych rodzinach grafów dowolnie podzielnych

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, będący w pewnym sensie uzupełnieniem referatu z października 2008, poświęcony jest przypomnieniu znanych faktów oraz kilku mocniejszym wersjom tego problemu. Szczegółowiej niż poprzednio omówione zostaną pewne rodziny grafów DP.

Serdecznie zapraszamy wszystkich chętnych!