Sekcja Strukturalnej Teorii Grafów działa pod opieką dr Moniki Pilśniak i zajmuje się otwartymi problemami między innymi z dziedziny kolorowań przełamujących automorfizmy w grafie oraz podziałów grafów. Zagadnienie, którym zajmujemy się ostatnio, to kolorowanie krawędziowe produktów prostego i silnego, przełamujące automorfizmy.
Definicja. Niech $$x,y$$ będą wierzchołkami grafu $$G$$. Mówimy, że $$x,y$$ są w relacji $$R$$, jeżeli spełniony jest warunek $$N(x) = N(y) $$. Graf $$G$$ nazywamy $$R$$-cienkim, jeżeli żadne dwa wierzchołki tego grafu nie są w relacji $$R$$.
Podobnie wierzchołki $$x,y$$ są w relacji $$S$$, jeżeli $$N(x) cup {x} = N(y) cup {y} $$. Graf $$G$$ nazywamy $$S$$-cienkim, jeżeli żadne dwa wierzchołki tego grafu nie są w relacji $$S$$.
Celem naszych prac jest udowodnienie hipotezy w takiej postaci jak poniżej (być może z trochę innym górnym ograniczeniem na rząd grafu $$H$$).
Hipoteza. Niech $$G,H$$ będą grafami $$R$$-cienkimi ($$S$$-cienkimi) spełniającymi warunek
$$2<|G|le |H| le 2^{|G|}(2^{||G||}-1) – |G|+1. $$
Wówczas indeks rozróżniający grafu $$Gtimes H$$ (odpowiednio $$G boxtimes H $$) jest równy co najwyżej 2, to znaczy istnieje takie kolorowanie krawędzi tego grafu dwoma kolorami, że jedynym automorfizmem zachowującym kolory wszystkich krawędzi jest identyczność.
Poprzednim obiektem badań członków koła był problem podziału grafów na żywo.
Definicja. Mówimy, że graf $$G$$ rzędu $$n$$ jest dowolnie podzielny, gdy dla dowolnego ciągu liczb naturalnych $$(n_1, n_2, dots, n_k)$$ takiego, że $$n_1+n_2+cdots+n_k = n$$, istnieje podział zbioru wierzchołków $$V(G) = V_1 cup dots cup V_k$$ taki, że $$|V_i|=n_i$$ oraz graf indukowany przez zbiór $$V_i$$ jest spójny, $$i=1,dots,k$$.
Graf jest dowolnie podzielny na żywo, jeśli taki podział da się wykonać, wybierając kolejno zbiory $$V_i$$, przy czym w chwili $$i$$ znamy tylko liczby $$n_1, dots, n_i$$.
Problem grafów dowolnie podzielnych był rozważany przez wielu matematyków, również z Katedry Matematyki Dyskretnej działającej przy naszym wydziale. Są to między innymi: Mariusz Woźniak, Rafał Kalinowski, Monika Pilśniak, Irmina Zioło, Antoni Marczyk oraz Jakub Przybyło. Szczególnie interesujące okazało się dla nas następujące twierdzenie.
Twierdzenie (Kalinowski, 2015+). Jeśli $$G$$ jest grafem, który spełnia jeden z poniższych dwóch warunków:
- $$sigma_2 (G) ge n-3$$
- $$||G|| > binom{n-3}{2}+6$$, $$nge 15$$ lub $$nle 7$$,
wówczas $$G$$ jest dowolnie podzielny wtedy i tylko wtedy, gdy jest dowolnie podzielny na żywo.
W efekcie badań naukowych pięciu członków koła, wykazaliśmy następujące twierdzenie.
Twierdzenie (Burkot, Bednarz, Dudzik, Kwaśny, Pawłowski, 2016+). Niech $$G$$ będzie grafem rzędu $$nin {8,dots, 14}$$ i rozmiaru większego niż $$binom{n-3}{2}+6$$. Wówczas $$G$$ jest dowolnie podzielny wtedy i tylko wtedy, gdy jest dowolnie podzielny na żywo.
Jest to więc uzupełnienie twierdzenia udowodnionego przez Kalinowskiego, prawdziwy jest zatem poniższy wniosek.
Wniosek. Niech $$G$$ będzie grafem rzędu $$n$$ i rozmiaru większego niż $$binom{n-3}{2}+6$$. Wówczas $$G$$ jest dowolnie podzielny wtedy i tylko wtedy, gdy jest dowolnie podzielny na żywo.
Spotkania sekcji odbywają się w czwartki o godzinie 12:00 w sali 325 w łączniku A3-A4.