Jarosław RYBAK

(WMS AGH)

Podziały na lasy liniowe w grafach kubicznych (Publiczna obrona pracy magisterskiej)

Lasem liniowym nazywamy graf, którego składowe są ścieżkami, zaś podziałem liniowym grafu $G$ podział jego zbioru krawędzi na lasy liniowe. $l_a$ jest minimalną liczbą lasów liniowych w podziale liniowym grafu $G$. W 1981 roku Jin Akiyama i Vasek Chvátal wykazali, że dla dowolnego grafu kubicznego $G$ zachodzi równość $l_a(G)=2$.

W referacie zostaną podane pewne nowe wyniki dotyczące hipotezy postawionej w 1987 roku przez Wormalda, mówiącej, że jeśli $G$ jest grafem kubicznym i $\vert G\vert\equiv 0$ (mod 4), wówczas istnieje podział liniowy $E(G)=L_B\cup L_R$ taki, że grafy indukowane przez zbiory krawędzi $L_B$ i $L_R$ są izomorficzne.

Serdecznie zapraszamy wszystkich chętnych !