Strona główna > Archiwalny program seminarium > 2018/2019
2018/2019
12.06
Stable Marriage and Stable Roommates: Optimality and Variants
Jacek Gładysz (Międzynarodowa Szkoła 2+2)
Streszczenie:
Adam Tyc (IMPAN)
Wariacje na temat hipotezy Roty
Co mówią wielomiany (o kolorowalności, wybieralności i malowalności grafów) - część 3.
Co mówią wielomiany (o kolorowalności, wybieralności i malowalności grafów) - część 2.
Co mówią wielomiany (o kolorowalności, wybieralności i malowalności grafów).
Well-quasi-order in classes of directed graphs
This is joint work with Maria Chudnovsky, S-il Oum, Paul Seymour and Paul Wollan.
Ułamkowe upakowania skierowanych cykli
Joint work with Roman Glebov and Jan Volec.
seminarium odwołane
05.06
Artur Giżycki
Mierzalna liczba chromatyczna lokalnie skończonych grafów borelowskich
29.05
Karolina Okrasa
Complexity of H-coloring on graphs with bounded treewidthStreszczenie
For a fixed graph H, the H-coloring problem asks if an instance graph G
admits a homomorphism to H. If a tree decomposition of G of width t is
given in the input, then the problem can be solved in time
t·nO(1) by dynamic programming. We will analyze for which H
this bound cannot be improved (assuming the Strong Exponential Time
Hypothesis). Also, we will show in which cases we were not able to prove
a tight bound for the complexity and how it relates to big open
problems in the algebraic graph theory.
This is based on a joint work with Paweł Rzążewski.
This is based on a joint work with Paweł Rzążewski.
22.05
Konstanty Junosza-Szaniawski
Problem multiprzepływu w sieciach
15.05
Jiehua Chen (Uniwersytet Warszawski)Stable Marriage and Stable Roommates: Optimality and Variants
Streszczenie:
The classic Stable Roommates problem (which is the non-bipartite generalization of the well-known Stable Marriage problem) asks whether
The classic Stable Roommates problem (which is the non-bipartite generalization of the well-known Stable Marriage problem) asks whether
there is a stable matching for a given set of agents, i.e., a partitioning of the agents into disjoint pairs such that
no two agents induce a blocking
pair. Herein, each agent has a
preference list denoting who she prefers to have as a partner, and two
agents form a blocking pair if they
prefer to be with each other rather
than with their assigned partners.
Since stable matchings may not be unique, we study an NP-hard optimization variant of Stable Roommates, called Egalitarian Stable
Since stable matchings may not be unique, we study an NP-hard optimization variant of Stable Roommates, called Egalitarian Stable
Roommates, which seeks to find a stable matching with a minimum
egalitarian cost γ, i.e., the sum of the dissatisfaction of the agents
is
minimum. The dissatisfaction of an agent is the number of agents that
this agent prefers over its partner if she is matched; otherwise it is
the length of its preference list. We also study almost stable
matchings, called Minimum Blocking Pair Stable Roommates, which seeks to
find a matching with a minimum number β of blocking pairs. Our main
result is that Egalitarian Stable Roommates parameterized by γ is
fixed-parameter tractable, while Min-Block-Pair Stable Roommates
parameterized by β is W[1]-hard, even if the length of each preference
list is at most five.
Finally (if time permits), we briefly discuss two generalized stability concepts for the Stable Marriage problem, which is the bipartite variant
Finally (if time permits), we briefly discuss two generalized stability concepts for the Stable Marriage problem, which is the bipartite variant
of the Stable Roommates problem where the agent set is partitioned into
two disjoint sets such that each agent from one set has a strict
preference
list that ranks a subset of the agents from the other set.
The first concept allows each agent to have multiple preference lists,
each ranking the
counterparts in a possibly different way. The second
concept allows to reason about the strength of the classic stability
when the agents'
preference may change slightly.
08.05
Paweł Twardowski (Politechnika Łódzka)Metoda wielomianowa dla kolorowania grafów zewnętrznie planaranych
24.04
Sylwia Cichacz (Akademia Górniczo-Hutnicza)Realizacja digrafów w skończonych grupach przemiennych
10.04
Hipoteza samotnego biegacza i rysowanie prostych
Streszczenie:
W referacie opowiem o dwóch problemach, które mają w pewnym sensie podobną strukturę. W obu przypadkach trochę wiemy lecz zdecydowanie więcej nie wiemy. Pierwszy problem to tytułowa hipoteza samotnego biegacza. Co do drugiego natomiast, pozostańmy przy stwierdzeniu, że dotyczy rysowania prostych.
Dokonam przeglądu dotychczas podjętych zmagań z omawianymi problemami, postaram się też zrobić niewielki krok w przód i spojrzeć na analizowane zagadnienia z trochę innego punktu widzenia. Okazuje się bowiem, że niby tak odległe od biegacza proste mogą jednak mieć z nim coś wspólnego. W przypadku rysowania prostych również postaram się zaproponować coś nowego tak by wyjść poza ramy oryginalnego problemu.
03.04
Z-zawiązane triangulacje powierzchni
Streszczenie:
Wielokąt Petriego w wielościanie foremnym jest znanym pojęciem geometrii klasycznej. Odpowiedniki wielokątów Petriego w grafach zanurzonych w powierzchnie znane są jako zygzaki. Obiekt posiadający dokładnie jeden zygzak nazywa się z-zawiązanym. Będziemy rozważali zygzaki w triangulacjach powierzchni (niekoniecznie orientowalnych). Pokażemy, że każda triangulacja dowolnej powierzchni może zostać rozdrobniona do z-zawiązanej triangulacji. Naszym głównym narzędziem będzie pojęcie z-monodromii (wzorowane na pojęciu monodromii występującym w teorii układów dynamicznych).
Wielokąt Petriego w wielościanie foremnym jest znanym pojęciem geometrii klasycznej. Odpowiedniki wielokątów Petriego w grafach zanurzonych w powierzchnie znane są jako zygzaki. Obiekt posiadający dokładnie jeden zygzak nazywa się z-zawiązanym. Będziemy rozważali zygzaki w triangulacjach powierzchni (niekoniecznie orientowalnych). Pokażemy, że każda triangulacja dowolnej powierzchni może zostać rozdrobniona do z-zawiązanej triangulacji. Naszym głównym narzędziem będzie pojęcie z-monodromii (wzorowane na pojęciu monodromii występującym w teorii układów dynamicznych).
27.03
Jarosław Grytczuk20.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ż 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ącCo 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
o 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 5).
o 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 5).
06.03
Mariusz ZającCo 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
o 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 5).
o 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 5).
27.02
Mariusz ZającCo 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
o 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 5).
o 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 5).
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.
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 |
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 k 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.
[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 2 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.
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.02
Mendezem i Wiechertem (https://arxiv.org/abs/1708.05
nieopublikowanych wynikach z Gwenem Joret.
07.11
Karolina OkrasaSubexponential 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.
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 u, v 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
mapping ϕ : V → {1, . . . , k} such that any two vertices u, v 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łane17.10
Paweł RzążewskiDrawing 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.
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