Ostatnia aktualizacja:
January 14. 2019 07:23: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.


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