Ostatnia aktualizacja:
March 17. 2019 17:38:19
Strona główna > Aktualny program seminarium

Aktualny program seminarium

Plan referatów może ulec zmianie. Jeśli chcesz otrzymywać regularnie aktualny plan referatów to napisz do sekretarza seminarium.


20.03
Jakub Przybyło (Akademia Górniczo-Hutnicza)
Inkluzyjny indeks chromatyczny grafu

Streszczenie:
W 2002 roku Zhang, Liu i Wang sformułowali hipotezę, iż krawędzie dowolnego grafu spójnego o przynajmniej sześciu wierzchołkach można pokolorować właściwie przy użyciu nie więcej niż Δ+2 barw tak, by sąsiednie wierzchołki otrzymały różne palety incydentnych z nimi kolorów. Przypuszczenie to zostało potwierdzone z dokładnością do stałej addytywnej przez Hatami’ego w 2005 roku, który użył metody probabilistycznej. Stosując podejście oparte o kompresję entropii, Joret i Lochet uzyskali w ostatnim czasie analogiczny rezultat lecz z istotnie poprawioną stałą addytywną. Przedmiotem mojego referatu będzie zagadnienie pokrewne do powyższego, gdzie oczekujemy silniejszej własności od właściwego kolorowania krawędziowego. Mianowicie, będziemy wymagać nie tylko aby palety sąsiednich wierzchołków były różne, ale dodatkowo by żadna nie zawierała się w drugiej. Przedstawię podstawowe różnice pomiędzy oboma problemami, główną hipotezę dotyczącą drugiego zagadnienia, jak i związane z nim znane wyniki.


13.03
Mariusz Zając
Co mówią wielomiany (o kolorowalności, wybieralności i malowalności grafów) - część 3.

Streszczenie:
Niedawne prace J. Grytczuka i X. Zhu pozwoliły uogólnić twierdzenie C. Thomassena
5-wybieralności grafów planarnych przy użyciu wielomianów grafowych.
Powiem więcej o związku pomiędzy własnościami wielomianów a różnymi rodzajami
kolorowalności grafów, co pozwoli zarówno inaczej spojrzeć na znane wyniki,
jak i nieco je rozszerzyć (np. klasy grafów planarnych na większą klasę
grafów bez minora K5).


06.03
Mariusz Zając
Co mówią wielomiany (o kolorowalności, wybieralności i malowalności grafów) - część 2.

Streszczenie:
Niedawne prace J. Grytczuka i X. Zhu pozwoliły uogólnić twierdzenie C. Thomassena
5-wybieralności grafów planarnych przy użyciu wielomianów grafowych.
Powiem więcej o związku pomiędzy własnościami wielomianów a różnymi rodzajami
kolorowalności grafów, co pozwoli zarówno inaczej spojrzeć na znane wyniki,
jak i nieco je rozszerzyć (np. klasy grafów planarnych na większą klasę
grafów bez minora K5).


27.02
Mariusz Zając
Co mówią wielomiany (o kolorowalności, wybieralności i malowalności grafów).

Streszczenie:
Niedawne prace J. Grytczuka i X. Zhu pozwoliły uogólnić twierdzenie C. Thomassena
5-wybieralności grafów planarnych przy użyciu wielomianów grafowych.
Powiem więcej o związku pomiędzy własnościami wielomianów a różnymi rodzajami
kolorowalności grafów, co pozwoli zarówno inaczej spojrzeć na znane wyniki,
jak i nieco je rozszerzyć (np. klasy grafów planarnych na większą klasę
grafów bez minora K5).


20.02
Irene Muzi (Uniwersytet Warszawski)
Well-quasi-order in classes of directed graphs

Streszczenie:
A set Q is well-quasi-ordered by a relation if for every sequence q1, q2, ... of elements of Q there exist i<j such that qi qj. In their Graph Minors series, Robertson and Seymour prove that graphs are well-quasi-ordered by the minor relation. This result, which is known as the Graph Minor Theorem, is considered one of the deepest results in graph theory and has several algorithmic applications.

Unfortunately, the same is not true for directed graphs and the relation of butterfly minor. In particular, we can easily identify two infinite antichains. We can then ask if classes of graphs that exclude these antichains are well-quasi-ordered by the butterfly minor relation. We prove that this is the case while at the same time providing a structure theorem for these graph classes.

This is joint work with Maria Chudnovsky, S-il Oum, Paul Seymour and Paul Wollan.


23.01
Zbigniew Lonc
O sprawiedliwym podziale dóbr na grafach

Streszczenie:
Przypuśćmy, że mamy m dóbr niepodzielnych i n agentów, którzy mają sprawiedliwie rozdzielić te dobra między siebie. Każde dobro ma pewną wartość dla każdego agenta, przy czym dane dobro może mieć różną wartość dla różnych agentów. Każdy agent x wyobraża sobie następujący protokół podziału zbioru dóbr pomiędzy n agentów: x dzieli zbiór dóbr na n części, każdy z pozostałych n-1 agentów wybiera którąś z tych części, a x bierze tę część, która zostanie na samym końcu. Oczywiście agent x dzieli zbiór dóbr tak, żeby dostać dobra o jak największej sumarycznej wartości niezależnie od wyborów innych agentów. Oznaczmy tę największą wartość przez m(x). Agent x uważa rzeczywisty podział za sprawiedliwy, jeśli dostanie dobra o wartości co najmniej m(x). Ten rzeczywisty podział nazywamy MMS-podziałem, jeśli każdy z n agentów uważa go za sprawiedliwy. Załóżmy teraz, że zbiór dóbr ma pewną strukturę. Dokładniej, dobra są wierzchołkami pewnego grafu G. Nie wszystkie podziały zbioru dóbr między n agentów są teraz dozwolone, lecz jedynie takie gdzie każdy agent dostaje zbiór dóbr indukujący spójny podgraf grafu G. Problem istnienia MMS-podziału jest trudny już nawet dla bardzo prostych grafów G. W referacie skoncentrujemy się na przypadku, gdy G jest cyklem. Ponieważ dla cykli MMS-podział nie zawsze istnieje, interesować nas będzie jak bardzo można się do niego zbliżyć, a dokładniej jaka jest największa stała c, 0<c<1, taka że istnieje podział zbioru dóbr, w którym każdy agent otrzymuje dobra o wartości co najmniej cm(x).


16.01
Jarosław Grytczuk
Graph polynomials and choosability of planar graphs

Streszczenie:
A famous theorem of Thomassen asserts that every planar graph is 5-choosable. Voigt proved that this result is optimal by exhibiting a non-4-choosable planar graph. We prove that from every planar graph one may delete a matching so that the resulting graph is 4-choosable. The proof uses graph polynomials and is based on Combinatorial Nullstellensatz of Alon.

Joint work with Xuding Zhu.



09.01
Paweł Rzążewski
Ułamkowe upakowania skierowanych cykli

Streszczenie:
Erdős i Pósa pokazali, że jeśli największa liczba wierzchołkowo rozłącznych cykli w grafie wynosi k, to istnieje zbiór f(k) wierzchołków, których usunięcie spowoduje usunięcie wszystkich cykli z grafu. Younger postawił hipotezę, że podobna własność zachodzi dla cykli skierowanych. Seymour rozważał ten problem dla ułamkowych upakowań cykli skierowanych i pokazał, że jeśli największe takie upakowanie ma wartość k, istnieje zbiór rozmiaru O(k log k loglog k), którego usunięcie spowoduje usunięcie wszystkich cykli (skierowanych) [1]. W ramach referatu udowodnię słabsze ograniczenie O(k^2), oparte na tym samym pomyśle, ale bez większości komplikacji technicznych (ten wynik też jest wspomniany w pracy [1]). Swoją drogą, hipoteza Youngera została potwierdzona przez Reeda, Robertsona, Seymoura i Thomasa [2], a ograniczenie na f(k) uzyskane przez nich jest funkcją-wieżą.

[1] P.D. Seymour, Packing directed circuits fractionally, Combinatorica 15 (1995), 281--288.
[2] B. Reed, N. Robertson, P. Seymour, R. Thomas, Packing directed circuits, Combinatorica 16 (1996), 535--554.



19.12
Jakub Przybyło (Akademia Górniczo-Hutnicza)
Łatwiej zderegularyzować grafy regularne
 
Streszczenie:
Słynna Hipoteza 1-2-3 sugeruje, iż krawędziom dowolnego grafu bez składowej K2 można nadać wagi ze zbioru  {1,2,3} tak, by sąsiednie wierzchołki otrzymały różne tzw. ważone stopnie. Problem ten pozostaje nierozwiązany. W ramach referatu udowodnię, iż hipoteza ta jest niemal prawdziwa w przypadku grafów regularnych.


12.12
Andrzej Grzesik (Uniwersytet Jagielloński)
Degree condition forcing oriented cycles of a given length
 
Streszczenie:
Motivated by the longstanding Caccetta-Häggkvist Conjecture, Kelly, Kühn and Osthus made a conjecture on the minimal semidegree forcing appearance of a directed cycle of a given length and proved it for some cases. In the talk we will present an overview of a proof of all the remaining cases of their conjecture. 

Joint work with Roman Glebov and Jan Volec. 


05.12
Pavel Dvořák (Charles University)
Parameterized approximation scheme for Steiner Tree Problem 

Streszczenie:
We will discuss parameterized complexity of Steiner Tree parameterized by the number of Steiner vertices in the optimal solution. I will talk about complexity of several version of this problem - unweighted/weighted and undirected/directed. But mainly I will talk about weighted undirected version of this problem. This version is APX-hard and W[2]-hard. I will present an approximation parameterized scheme for this problem, i.e. an algorithm which runs in FPT time and returns an (1+ε)-approximation of the optimum for every ε>0.


28.11
Jana Novotná (Charles University)
List 3-Colouring is polynomial for (P3+P4)- and (P2+P5)-free graphs 

Streszczenie:
The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L(u) ⊆ {1, . . . , k}, then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. The graph Pr + Ps is the disjoint union of the r-vertex and the s-vertex path. 

We prove that List 3-Colouring is polynomial-time solvable for (P2 + P5)-free graphs and for (P3 + P4)-free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices. 

In the talk I show you properties of a common super class, (P3+P5)-free graphs, and steps of branching that leads eventually to a polynomial number of polynomial-time solvable instances of 2-List Coloring problem, and thus prove the promised theorem. 


21.11
Grzegorz Gutowski (Uniwersytet Jagielloński)
Kompresja entropii w problemie acyklicznego kolorowania krawędzi

Streszczenie:
Przedstawię nowe usprawnienia w technice kompresji entropii pozwalające na pobicie bariery 4Δ w problemie acyklicznego kolorowania krawędzi.


14.11
Piotr Micek (Uniwersytet Jagielloński)
Słabe liczby kolorujące: ograniczenia i zastosowania

Streszczenie
Słabe (i silne) liczby kolorujące zostały zaproponowane przez
Kiersteada i Yanga w 2003 r., choć już wcześniej pojawiały się
implicite w kilku niezaleźnych miejscach. Ich znaczenie wzrosło, gdy w
2009 r. Zhu wykazał, że klasa grafów ma ograniczoną ekspansję wtedy i
tylko wtedy, gdy dla każdej liczby r≥1 r-ta liczba kolorująca grafów
z klasy jest ograniczona funkcją od r. Co więcej, spośród wielu
charakteryzacji rzadkich klas grafów, często to liczby kolorujące są
najwygodniejszym narzędziem do pracy w zastosowaniach.

W celu oswojenia z liczbami kolorującymi zobaczymy, jak użyć
ograniczeń na te liczby, aby efektywnie pokolorować grafy p-odległości
grafów planarnych (graf p-odległości podanego grafu to graf na tych
samych wierzchołkach, co wyjściowy graf ale z krawędziami pomiędzy
wierzchołkami odległymi o dokładnie p w wyjściowym grafie). Później
zobaczymy dowód ograniczający wymiar częściowych porządków w terminach
liczb kolorujących ich grafów pokryć.

Porozmawiamy również o najlepszych znanych ograniczeniach na liczby
kolorujące dla naturalnych klas grafów, takich jak grafy planarne czy
zewnętrznie planarne. Zobaczymy kilka dowodów/konstrukcji
ilustrujących najważniejsze pomysły oraz hipotezę, która kosztowała
mnie już wiele bezsennych nocy.

Prezentowany materiał będzie oparty głównie na wynikach z pracy
Kiersteada, van den Heuvela i Quiroza
(https://arxiv.org/abs/1612.02160), z mojej pracy z Joret, Ossoną de
Mendezem i Wiechertem (https://arxiv.org/abs/1708.05424) oraz moich
nieopublikowanych wynikach z Gwenem Joret.


07.11
Karolina Okrasa
Subexponential algorithms for variants of homomorphism problem in string graphs

Streszczenie
A homomorphism h from G to H is called locally injective (bijective, surjective, resp.) if for every v ∈ V (G) it induces an injective (bijective, surjectve) mapping between the neighborhood of v and the neighborhood of h(v). For a fixed H, we denote by LIHom(H) (LBhom(H), LSHom(H), respectively) the computational problem of determining the existence of a locally injective (bijective, surjectve) homomorphism from a given graph G to H. I will show that if G is a string graph, then LIHom(H) and LBHom(H) problems can be solved in subexponential time for every H. I will also show the complexity classification for LSHom(H) if H is a simple graph of maximum degree at most 2.

This is based on a joint work with Paweł Rzążewski (https://arxiv.org/pdf/1809.09345.pdf).


31.10
Tomáš Masařík (Charles University and University of Warsaw)
Complexity of packing coloring

Streszczenie
A packing k-coloring for some integer k of a graph G = (V, E) is a
mapping ϕ : V → {1, . . . , k} such that any two vertices uv of
color ϕ(u) = ϕ(v) are in distance at least ϕ(u) + 1. This concept is
motivated by frequency assignment problems. The packing chromatic
number of G is the smallest k such that there exists a packing
k-coloring of G.

Fiala and Golovach [Complexity of the packing coloring problem for
trees, DAM 158:7 2010, 771-778] showed that determining the packing
chromatic number for chordal graphs is NP-complete for diameter
exactly 5. While the problem is easy to solve for diameter 2, we show
NP-completeness for any diameter at least 3. Our reduction also shows
that the packing chromatic number is hard to approximate within n
1/2−ε for any ε > 0.

In addition, we design an FPT algorithm for interval graphs of bounded
diameter. This leads us to exploring the problem of finding a partial
coloring that maximizes the number of colored vertices. We also
present some approaches to tackle the problem on (unit) interval
graphs. However, the main complexity classification there remains
open.

This is joint work with Minki Kim, Bernard Lidický, and Florian Pfender


24.10
seminarium odwołane


17.10
Paweł Rzążewski
Drawing graphs and hypergraphs in 3d

Streszczenie:
Abstrakt: By Fáry's theorem, every planar graph has a non-crossing embedding in the plane, in which every edge is drawn as a straight-line segment. On the other hand, it is well-known that every graph has a non-crossing straight-line embedding in 3d. I will survey some questions and results concerning drawing graphs in 3d. Then I will show some new results, concerning representing graphs and their dual hypergraphs by convex polygons in 3d.

The new results are obtained with William Evans, Chan-Su Shin, Noushin Saeedi, and Alexander Wolff.


10.10
seminarium odwołane


03.10
seminarium odwołane