Monika PSZCZOŁA

(Politechnika Warszawska)

Dekompozycje krawędziowe grafów

Niech $\cal H$ będzie rodziną grafów. $\cal H$-dekompozycją grafu $G$ nazywamy podział zbioru krawędzi $G$ na podzbiory indukujące podgrafy izomorficzne z elementami $\cal H$.

W referacie będzie omówiona złożoność obliczeniową problemu istnienia $\cal H$-dekompozycji grafu $G$ w przypadku, gdy $\cal H$ zawiera graf $K_{1,2}$ oraz w przypadku, gdy elementami $\cal H$ są grafy trzykrawędziowe.

Serdecznie zapraszamy wszystkich chętnych !