Strona główna > Archiwalny program seminarium > 2022/2023
2022/2023
14.06
Katarzyna Rembelska
Uczenie maszynowe - podstawy oraz zastosowania w matematyce
Streszczenie:
Zacznę od podstaw, słownictwa, powiem czym tak naprawdę jest uczenie maszynowe, jakie są metody uczenia oraz czym się różni uczenie maszynowe od uczenia głębokiego czy sztucznej inteligencji. Postaram się pokazać najważniejsze zagadnienia uczenia maszynowego, przekazać sposoby oraz narzędzia, które ułatwią dalszą zabawę w tym obszarze.
Następnie skupie się na przedstawieniu wybranych metod uczenia maszynowego, które przyniosły przynajmniej częściowe sukcesy w niektórych działach matematyki.
07.06
Konstanty Junosza-Szaniawski
Problem rozmieszczenia kontrolerów jako gra kombinatoryczna między operatorem sieci, a atakującym
Streszczenie:
Problem rozmieszczenia kontrolerów w sieci telekomunikacyjnej, tak aby sieć była odporna na ataki można przedstawić jako grę kombinatoryczną na grafie. Przestawię algorytm znajdujący optymalne strategie dla obu graczy.
31.05
Grzegorz Gutowski
Approach to List Coloring Planar Graphs
Abstract:
In my talk I present some recent work on problems related to choosability of planar graphs.
My intention is to present how "via Combinatorial Nullstellensatz" approach can be applied to strengthen some results while simplifying their proofs.
24.05
Marta Piecyk
Indukowane skojarzenia w produktach grafów
Streszczenie:
Dla grafów G, H produktem prostym GxH nazywamy graf, którego zbiorem wierzchołków jest V(G)xV(H), a (u,v)(x,y) jest krawędzią wtedy i tylko wtedy, gdy ux jest krawędzią w G i vy jest krawędzią w H. Przez mim(H) oznaczamy rozmiar największego indukowanego skojarzenia w H i definiujemy mimsup(H):=sup_{k in N} mim(H^k)^1/k, gdzie H^k to produkt prosty k kopii grafu H, tj. Hx...xH.
Parametr mimsup(H) pojawił się w naturalny sposób przy badaniu złożoności obliczeniowej problemu homomorfizmu grafów. Podczas referatu opowiem o związkach mimsup z innymi znanymi parametrami grafowymi.
Parametr mimsup(H) pojawił się w naturalny sposób przy badaniu złożoności obliczeniowej problemu homomorfizmu grafów. Podczas referatu opowiem o związkach mimsup z innymi znanymi parametrami grafowymi.
17.05
Andrzej Grzesik
Tęczowe problemy Turána
Streszczenie:
W tęczowym wariancie problemu Turána rozważamy k grafów na tym samym zbiorze wierzchołków i chcemy wyznaczyć najmniejszą możliwą liczbę krawędzi w każdym grafie, która wymusza pojawienie się kopii zadanego grafu F zawierającej co najwyżej jedną krawędź z każdego grafu. Innymi słowy, traktujemy każdy z k grafów jako graf w jednym z k kolorów i rozważamy ile musi być krawędzi w każdym kolorze, żeby pojawiła się tęczowa kopia zadanego grafu F.
Na wykładzie przedstawimy znane rezultaty dotyczące tego zagadnienia, a także zaprezentujemy najnowsze wyniki, uzyskane wspólnie z Sebastianem Babińskim i Magdaleną Prorok, rozwiązujące tęczowy problem Turána dla ścieżki na 4 wierzchołkach oraz skierowanego trójkąta przy dowolnej liczbie kolorów.
10.05 - seminarium zdalne
Jan Goedgebeur
An introduction to computational graph theory and generation algorithms
Abstract:
Computers are often used in combinatorics to determine if combinatorial objects with given structural or extremal properties exist as these existence problems are often too complex to solve by hand. This is done by designing and implementing generation algorithms which construct combinatorial objects from a given class (typically avoiding the generation of isomorphic copies) and analysing the resulting objects.
In this talk we will give an introduction to computational graph theory and the design of generation algorithms in particular. We will also give concrete examples of how these generation algorithms have helped to gain new insights and solve problems in mathematics and in chemistry.
In this talk we will give an introduction to computational graph theory and the design of generation algorithms in particular. We will also give concrete examples of how these generation algorithms have helped to gain new insights and solve problems in mathematics and in chemistry.
26.04
Marcin Anholcer
O acyklicznych b-kolorowaniach
Streszczenie:
Jeden z przybliżonych algorytmów kolorowania grafów polega na wykonywaniu tak długo, jak to możliwe, tzw. kroków przekolorowujących. Każdy taki krok polega na przekolorowaniu wszystkich wierzchołków wybranego koloru na inne kolory występujące w kolorowaniu (w szczególności na jeden inny kolor). Liczba b-chromatyczna to największa liczba kolorów, przy jakiej algorytm może skończyć działanie. Obiektem naszego zainteresowania jest analogiczny problem, w którym ograniczamy się do kolorowań acyklicznych. W referacie przedstawię definicje i różne oszacowania dla acyklicznej liczby b-chromatycznej, a także nieco dokładniejszych wyników dla wybranych rodzin grafów.
19.04
Bartłomiej Pawlik
Przetasowane kwadraty
Streszczenie:
Jednym z ciekawszych obiektów w kombinatoryce na słowach są przetasowane kwadraty (ang. shuffle squares). Pojęcie wprowadzone dekadę temu przez Henshalla, Rampersada i Shallita [3] wciąż jest słabo zbadane. Przykładowo, nie jest znany wzór jawny na liczbę przetasowanych kwadratów danej długości, choć dysponujemy pewną asymptotyką [2] - w szczególności, nie wiadomo ile jest binarnych przetasowanych kwadratów długości 2n już dla n=20 [4]. W referacie zostanie przedstawiony dotychczasowy stan wiedzy na temat przetasowanych kwadratów [2,3], a następnie poruszymy temat drobnych uzupełnień i nieśmiałych uogólnień [1]. Skupimy się przede wszystkim na przypadku binarnym.
[1] J. Grytczuk, B. Pawlik, M. Pleszczyński, Variations on shuffle squares, w przygotowaniu
[2] X. He, E. Huang, I. Nam, and R. Thaper, Shuffle Squares and Reverse Shuffle Squares, arXiv preprint arXiv:2019.12455, (2021)
[3] D. Hanshall, N. Rampersad, and J. Shallit, Shuffling and Unshuffling, Bulletin of EATCS 107 (2012), 131-142
[4] https://oeis.org/A191755 (widziano 12 kwietnia 2023 r.)
12.04 - seminarium zdalne
Borut Lužar
Combining proper and square colorings
Abstract:
Proper colorings of graphs with additional distance constraints are an attractive topic in both settings: the vertex and the edge coloring. In particular, when we require that two vertices are colored differently if they are at distance at most 2, we are essentially coloring the square of a graph. Similarly, in a proper coloring of edges where two edges are colored differently as soon as they are adjacent or two of their endvertices are at distance 1, we are coloring the square of the line graph of a graph. We usually refer to the former as the square coloring and to the latter as the strong edge coloring.
Motivated by the notion of S-packing coloring, we will consider colorings with two types of colors: proper colors, which will be allowed to appear on two non-adjacent objects (regarding the setting-vertex or edge coloring), and strong colors, with which we will be able to color objects at distance at least 3 (in the edge coloring setting, the distance between two edges is taken as the distance between the corresponding vertices in the line graph). This combination of color types positions us in between the proper and the square colorings, which in most of the cases makes determination of the corresponding chromatic indices harder, but it also reveals several nice properties.
In the talk, we will focus mainly to coloring subcubic graphs and review recent results and the most interesting open problems on the topic in the vertex and the edge coloring settings.
29.03 - seminarium zdalne
Sylwia Antoniuk
O losowych rozszerzeniach grafów Diraca
Streszczenie:
Losowe rozszerzenie grafu (randomly perturbed/augmented graph) to model grafu, który powstaje poprzez dodanie losowych krawędzi do zadanego grafu G o n wierzchołkach, przy czym dodawane krawędzie losujemy niezależnie od siebie z prawdopodobieństwem p=p(n). W typowych rozważaniach graf G ma pewne deterministyczne własności, tj. ograniczenie dolne na minimalny stopień. Wówczas interesuje nas jaka wartość p z dużym prawdopodobieństwem zagwarantuje rozpatrywaną przez nas własność grafową, np. pojawienie się cyklu Hamiltona lub określonej faktoryzacji. Tym samym model ten stoi na pograniczu problemów Diraca oraz zagadnień z dziedziny grafów losowych, a co za tym idzie jest kopalnią ciekawych problemów do zbadania. W swoim referacie opowiem o ostatnich wynikach dotyczących tego modelu oraz o typowych metodach wykorzystywanych przy pracy z nim.
22.03
Paweł Rzążewski
Homomorfizmy grafów uporządkowanych
Streszczenie:
W ciągu ostatnich kilku lat pewną popularność zdobyły warianty klasycznych problemów grafowych umiejscowione w świecie grafów uporządkowanych, tj. z zadanym porządkiem liniowym na wierzchołkach. Ekscytujące wyniki w tym nurcie widzieliśmy także na naszym seminarium.
Jak w tym świecie wyglądają homomorfizmy grafów? Niech G i H będą grafami uporządkowanymi. Funkcję f : V(G) -> V(H) nazywamy homomorfizmem, jeśli
* jest homomorfizmem w zwykłym sensie, czyli krawędzie G są mapowane na krawędzie H,
* zachowuje porządki na wierzchołkach, tj. dla każdych dwóch wierzchołków u,v grafu G, jeśli u <= v, to f(u) <= f(v).
Podczas referatu omówimy kilka dość zaskakujących własności homomorfizmów grafów uporządkowanych (zaskakujących przez ich kontrast z analogami w świecie grafów nieuporządkowanych).
Jak w tym świecie wyglądają homomorfizmy grafów? Niech G i H będą grafami uporządkowanymi. Funkcję f : V(G) -> V(H) nazywamy homomorfizmem, jeśli
* jest homomorfizmem w zwykłym sensie, czyli krawędzie G są mapowane na krawędzie H,
* zachowuje porządki na wierzchołkach, tj. dla każdych dwóch wierzchołków u,v grafu G, jeśli u <= v, to f(u) <= f(v).
Podczas referatu omówimy kilka dość zaskakujących własności homomorfizmów grafów uporządkowanych (zaskakujących przez ich kontrast z analogami w świecie grafów nieuporządkowanych).
08.03
Małgorzata Śleszyńska-Nowak
Silna właściwa spójność grafów
Streszczenie:
W silnym kolorowaniu krawędzi grafu G wymagamy aby każda klasa koloru tworzyła skojarzenie indukowane w G, tzn. że nie tylko sąsiednie krawędzie muszą mieć różne kolory, ale także krawędzie połączone wspólną krawędzią. Opowiem o nowym wariancie spójnego kolorowania grafów opartego właśnie na silnym kolorowaniu.
Pokolorowany krawędziowo graf jest silnie właściwie spójny, jeżeli każde dwa wierzchołki są połączone co najmniej jedną silnie pokolorowaną ścieżką. Zastanowimy się ile kolorów musimy użyć do pokolorowania krawędzi grafu aby był on silnie właściwie spójny. Przedstawię aktualny stan wiedzy na ten temat. Pokażę również co wiemy o innych wariantach spójnego kolorowania.
Współautorzy: Michał Dębski, Jarosław Grytczuk, Paweł Naroski.
22.02
Jarosław Grytczuk
O problemie pokrycia kliki biklikami
Streszczenie:
Klikę na stu wierzchołkach pokrywamy grafami pełnymi dwudzielnymi (biklikami). Ile biklik potrzeba jeżeli każda krawędź ma być pokryta dokładnie raz? To wiadomo - 99. A ile biklik potrzeba jeżeli każda krawędź ma być pokryta raz lub dwa razy? Tego dokładnie nie wiadomo, może 16, a może 15. Opowiem co w tej kwestii udało się niedawno ustalić.
Współautorzy: Noga Alon, Andrzej P. Kisielewicz, Krzysztof Przesławski
25.01
Konstanty Junosza-Szaniawski
Aproksymacja rozpiętości L(2,1)-etykietowania grafów przecięć dysków jednostkowych
Streszczenie:
Etykietowanie L(2,1) to przypisanie wierzchołkom nieujemnych liczb całkowitych w taki sposób aby sąsiednie wierzchołki otrzymały etykiety różniące się co najmniej o 2, a wierzchołki w odległości 2 otrzymały różne etykiety. Graf przecięć dysków jest to graf dla którego istnieje rodzina dysków o średnicy 1 na płaszczyźnie taka, że możemy utożsamić dyski z wierzchołkami, a krawędź łączy dwa wierzchołki wtedy i tylko wtedy gdy odpowiadające im dyski się przecinają. Przedstawię algorytm 8-approksymacyjny dla etykietowania L(2,1) grafów przecięć dysków jednostkowych autorstwa Hirotaka Ono, Hisato Yamanaka [1]. Poprzedni najlepszy algorytm miał współczynnik aproksymacji 8.55 i jest autorstwa J.Chybowskiej-Sokół, KJS i P.Rzążewskiego [2].
[1] https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4282549
[2] J.Chybowska-Sokół, K.Junosza-Szaniawski, P.Rzążewski, L(2,1)-labeling of disk intersection graphs, Discrete Applied Mathematics 2019, https://doi.org/10.1016/j.dam.2019.08.020
18.01
Hubert Grochowski
Częściowe kolorowania pakujące i kolorowanie prawie pakujące siatki trójkątów
Streszczenie:
W wariancie pakującym kolorowania grafów wierzchołkom przyporządkowujemy dodatnie liczby naturalne, a gdy dwa wierzchołki otrzymują tę samą liczbę, to ich odległość grafowa jest od tej liczby większa. Szeroką klasą grafów, dla której bada się ten wariant kolorowania są grafy definiowane w sposób geometryczny. Finbow i Rall w 2010 roku pokazali, że nieskończonej siatki trójkątów nie da się pokolorować w sposób pakujący na skończoną liczbę kolorów. Można zadać sobie w takim razie pytanie - czy przez niewielkie osłabienie warunku na odległość w kolorowaniu pakującym jesteśmy już w stanie pokolorować w ten sposób rozważaną siatkę? Bądź też jak dużą część tej siatki jesteśmy w stanie pokolorować dysponując ustalonym zbiorem kolorów? Na te pytania postaramy się odpowiedzieć.
Wyniki wspólne z Konstantym Junoszą - Szaniawskim.
11.01
Dušan Knop
Balancing the Spread of Two Opinions in Sparse Social Networks
Abstract:
Inspired by the famous Target Set Selection problem, we propose a new discrete model for simultaneously spreading several opinions within a social network and perform an initial study of its complexity. Here, we are given a social network, a seed-set of agents for each opinion, and two thresholds for each agent. The first threshold represents the willingness of an agent to adopt an opinion if the agent has no opinion at all, while the second threshold states for willingness to acquire second opinion. The goal is to add as few agents as possible to the initial seed-sets such that, once the process started with these seed-sets stabilizes, each agent has either both opinions or none.
We show that the problem is NP-hard. Further, we investigate the complexity from the parameterized point-of-view. The problem is W[1]-hard with respect to the solution size. The problem remains W[1]-hard even for the combination of parameters the solution size and treewidth of the network even if all thresholds are at most 3, or the activation process stabilizes within 4 rounds. On the other hand, the problem is FPT when parameterized by the number of rounds, maximum threshold, and treewidth. This algorithm applies also for combined parameter treedepth and maximum threshold. Finally, we show that the problem is FPT when parameterized by vertex cover number of the input network alone. Our results also imply that the original Target Set Selection problem is FPT when parameterized by 3-PVC or Vertex-Integrity.
Joint work with Ondřej Suchý and Šimon Schierreich.
21.12
Tomáš Madaras
On (omni)present and (largely) missing cycles in plane graphs
Abstract:
One of "typical" directions in research of structure of graphs - both general ones and planar or planar-like ones as well - concern the presence / absence of cycles of particular fixed lengths. We address these questions for various families of planar and plane graphs, and present selected positive results (which are proved using the Discharging Method) and the constructions leading to infinite families of plane graphs with missing cycles of certain lengths.
14.12
Karolina Okrasa
Minimalne obstrukcje dla problemu homomorfizmu grafów
Streszczenie:
Powiemy, że graf G jest (wierzchołkowo-)k-krytyczny, jeśli liczba chromatyczna G wynosi k, ale dla każdego v in V(G) liczba chromatyczna grafu G-v jest mniejsza niż k.
Dla danej dziedzicznej klasy grafów C i liczby k>=0, przez Z(C,k+1) oznaczamy zbiór wszystkich grafów k-krytycznych, które należą do C. Podczas referatu opowiem, dla jakich par (C,k) zbiór Z(C,k) jest skończony, pokażę uogólnienie tego pojęcia na problem homomorfizmu grafów, częściowe wyniki z tym związane oraz kilka problemów otwartych.
30.11
Agata Pilitowska
O liczbie 2-reduktywnych raków i 2-permutacyjnych rozwiązań równania Yanga-Baxtera
Streszczenie:
Tzw. teorio-mnogościowe rozwiązania równania Yanga-Baxtera są w jedno-jednoznacznej odpowiedniości z tzw. birackami - algebrami o strukturze dwóch jednostronnych quasigrup, spełniającymi pewne dodatkowe równości.
Tematem prezentacji będą tzw. inwolutywne 2-permutacyjne rozwiązania równania Yang-Baxtera. Takie rozwiązania dzielą się na dwie klasy - dystrybutywne i niedystrybutywne. Rozdzielne można skutecznie skonstruować z grup abelowych i macierzy stałych. Stosując taką konstrukcję, można efektywnie policzyć wszystkie rozdzielne rozwiązania małych rzędów (do rozmiaru 14). Rozwiązania niedystrybutywne można również łatwo skonstruować z rozdzielnych przy pomocy dodatkowych permutacji.
Wyniki te są ściśle powiązane z liczbą tzw. raków (racks) i 2-reduktywnych raków.
23.11
Jarosław Grytczuk
Skojarzenia uporządkowane
Streszczenie:
Skojarzenia uporządkowane można interpretować jako słowa, w których każda litera występuje dokładnie dwa razy. Na przykład, ABCCADBD. Dwie pary liter mogą tworzyć trzy różne skojarzenia uporządkowane (tak zwane wzorce): (1) AABB (linia), (2) ABBA (stos) i (3) ABAB (fala).
Zachodzi następujące twierdzenie: Każde skojarzenie rozmiaru (n-1)^3 + 1 zawiera skojarzenie rozmiaru n, którego każda para liter tworzy ten sam wzorzec (albo linię, albo stos, albo falę). Podobne twierdzenie zachodzi dla ogólniejszych skojarzeń, w których każda litera występuje dokładnie r razy. Na przykład, dla r = 3 mamy 10 różnych wzorców utworzonych z par literowych tercetów: AAABBB, AABABB, ABABAB, itd., ale tylko 9 z nich tworzy wzorce kolektywne (pozwalające na budowę dowolnie dużego skojarzenia o parach mających ten sam wzorzec).
Wyniki pochodzą z pracy, której współautorami są Andrzej Dudek i Andrzej Ruciński: https://arxiv.org/abs/2210.14042
16.11
Sylwia Cichacz-Przeniosło
Grupy grafowo serdeczne
Streszczenie:
Jeśli A jest grupą przemienną, to etykietowanie f: V(G) -> A wierzchołków grafu G indukuje etykietowanie krawędzi grafu G, mianowicie krawędź uv otrzymuje etykietę f(u) + f(v) z A. Graf G jest A-serdeczny, jeśli istnieje takie etykietowanie f wierzchołków, że (1) klasy etykiet wierzchołków różnią się rozmiarem co najwyżej o jeden i (2) indukowane klasy etykiet krawędzi różnią się rozmiarem co najwyżej o jeden.
W literaturze badane jest głównie A-serdeczne etykietowanie dla grupy cyklicznej. Patrias i Pechenik badali większą klasę skończonych grup przemiennych. Postawili hipotezę, że dla każdej grupy A istnieje A-serdeczne etykietowanie dla prawie każdej ścieżki. Podczas referatu przedstawię rozwiązanie tej hipotezy. Ponadto pokażę, że wszystkie cykle są A-serdeczne dla każdej grupy przemiennej A nieparzystego rzędu. Wynik ten implikuje, że w dowolnej grupie przemiennej A rzędu nieparzystego możemy znaleźć tęczowy cykl dowolnej długości większej niż 2 i mniejszej niż |A|+1.
02.11
Michał Dębski
Prawie sprawiedliwe podziały grafów
Streszczenie:
Dany jest graf spójny G, który chcemy podzielić pomiędzy n agentów tak, aby każdy agent otrzymał zbiór wierzchołków indukujący spójny podgraf G. Każdy wierzchołek ma dla każdego agenta określoną nieujemną wartość. Mówimy, że taki podział jest c-sprawiedliwy (lub: jest c-mms-alokacją), jeżeli każdy z agentów otrzyma wierzchołki o sumarycznej wartości wynoszącej przynajmniej c razy mms_i, gdzie mms_i jest sprawiedliwym udziałem który powinien przypadać temu agentowi według pewnego kryterium sprawiedliwości (zostanie ono zdefiniowane podczas referatu).
Chcielibyśmy rozstrzygnąć, czy istnieje dodatnia stała c taka, że dla dowolnego grafu i dowolnej liczby agentów zawsze istnieje c-mms-alokacja, ale nie potrafimy tego zrobić; skupimy sie więc na pewnych szczególnych przypadkach tego problemu.
26.10
Zbigniew Lonc
Prawie sprawiedliwe podziały grafu pomiędzy trzech agentów
Streszczenie:
Zbiór pewnej liczby niepodzielnych dóbr ma zostać podzielony sprawiedliwie pomiędzy n agentów. Każde dobro ma dla każdego agenta określoną wartość, przy czym te wartości dla różnych agentów mogą być zupełnie inne. Zakładamy, że zbiór dóbr ma strukturę spójnego grafu, w którym dobra są wierzchołkami. Każdy agent wymaga, aby zbiór dóbr, które otrzyma w wyniku podziału, indukował w tym grafie podgraf spójny. Ponadto agent będzie zadowolony z podziału, jeśli otrzyma dobra o sumarycznej wartości nie mniejszej od wartości pewnego parametru, zwanego mm-udziałem (ang. maximin share) obliczanego osobno dla każdego agenta. (Definicja mm-udziału zostanie podana podczas referatu.) Podział grafu dóbr na n spójnych podgrafów rozdzielonych pomiędzy n agentów nazwiemy sprawiedliwym (albo mms-alokacją), jeśli każdy agent będzie z tego podziału zadowolony. Wiadomo, że każdy spójny graf dóbr można sprawiedliwie podzielić pomiędzy dwóch agentów. Jednak dla trzech agentów taki podział może nie istnieć nawet, jeśli graf dóbr jest grafem pełnym. Podczas referatu pokazane zostanie, że każdy spójny graf daje się tak podzielić pomiędzy trzech agentów, aby każdy agent dostał spójny podgraf o sumarycznej wartości jego wierzchołków nie mniejszej niż 3/4 jego mm-udziału.
19.10
Zofia Miechowicz
Równoczesne kolorowanie grafów
Streszczenie:
Przedstawimy ciekawy wariant kolorowania grafów zaproponowany przez R.Aharoniego, E. Bergera, M. Chudnovsky, F. Haveta i Z. Jianga. Niech dana będzie rodzina grafów (G1,…,Gm) na tym samym zbiorze wierzchołków. Kolorowaniem równoczesnym tej rodziny nazywać będziemy taki podział zbioru wierzchołków I1,…,Im, w którym każdy zbiór Ii jest niezależny w grafie Gi. Zobrazujemy problem dla pewnych szczególnych klas grafów, oraz przedstawimy jego naturalne uogólnienie na matroidy wraz z ciekawym, niepublikowanym dotąd, twierdzeniem, które wiąże ten problem z klasycznym twierdzeniem Seymoura o kolorowaniu matroidów.
12.10
Marta Piecyk
W_5-kolorowanie grafów z zabronionymi indukowanymi podgrafami
Streszczenie:
Homomorfizmem z grafu G w graf H (inaczej H-kolorowaniem grafu G) nazywamy funkcję f: V(G) -> V(H), która zachowuje krawędzie. Dla grafu F, powiemy, że G jest F-wolny, jeśli nie zawiera F jako podgrafu indukowanego.
Będziemy rozważać problem PrecoloringExt(H), w którym graf H jest ustalony, a na wejściu dany jest graf G razem z podzbiorem jego wierzchołków X oraz funkcją g: X -> V(H) (czyli prekolorowanymi wierzchołkami), i pytamy, czy g można rozszerzyć do homomorfizmu z G w H. Pokażę dość nietypowe zachowanie złożoności obliczeniowej tego problemu w przypadku, gdy H=W_5, w klasie grafów F-wolnych, dla pewnych grafów F.
Są to wspólne wyniki z Michałem Dębskim, Zbigniewem Loncem, Karoliną Okrasą i Pawłem Rzążewskim
05.10
Alexander Wolff
Coloring Mixed and Directional Interval Graphs
Abstract:
A mixed graph has a set of vertices, a set of undirected egdes, and a set of directed arcs. A proper coloring of a mixed graph G is a function c that assigns to each vertex in G a positive integer such that, for each edge uv in G, c(u) ≠ c(v) and, for each arc uv in G, c(u)<c(v). For a mixed graph G, the chromatic number of G is the smallest number of colors in any proper coloring of G.
A directional interval graph is a mixed graph whose vertices correspond to intervals on the real line. Such a graph has an edge between every two intervals where one is contained in the other and an arc between every two overlapping intervals, directed towards the interval that starts and ends to the right. Coloring such graphs has applications in routing edges in layered orthogonal graph drawing according to the Sugiyama framework; the colors correspond to the tracks for routing the edges.
We show how to compute the chromatic number of directional interval graphs efficiently. On the other hand, for mixed interval graphs, i.e., interval graphs where two intersecting intervals can be connected by an edge or by an arc in either direction arbitrarily, we prove that computing the chromatic number is NP-hard. In our paper (but not in my talk) we also show how to recognize directional interval graphs.
This is joint work with Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter, Joachim Spoerhase, and Johannes Zink.