Previous seminars
04.06.2019 16:15 Jarosław Grytczuk Politechnika Warszawska |
Graph polynomials and choosability |
A result of Thomassen asserts that every planar graph is 5-choosable (colorable from arbitrary lists of size 5 preassigned to the vertices of a graph). We prove that every planar graph has a matching whose deletion gives a 4-choosable graph. The proof is based on Combinatorial Nullstellensatz - a famous algebraic result of Alon involving multivariable polynomials. We also discuss possible applications of this method to other graph coloring problems, like the four color problem or the empire coloring problem, for instance.
Joint work with Xuding Zhu. |
26.02.2019 16:15 Marcin Briański |
Measuring sparsity (based on the lecture by M. Pilipczuk and S. Siebertz) |
15.01.2019 16:15 Marcin Briański |
Measuring sparsity (based on the lecture by M. Pilipczuk and S. Siebertz) |
08.01.2019 16:15 Bartosz Wodziński |
Algorithmic barriers from phase transitions (Dimitris Achlioptas, Amin Coja-Oghlan) |
18.12.2018 16:15 Maciej Czerwiński |
Lovasz meets Weisfeiler and Leman (by Dell, Grohe and Rattan) |
"In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k -dimensional generalization known as the Weisfeiler-Leman algorithm." |
27.11.2018 16:15 04.12.2018 16:15 Dominika Salawa, Kamil Kropiewnicki |
Representative sets in matroids (based on chapter of 'Parameterized algorithms') |
20.11.2018 16:15 Dawid Tracz |
Finding Cliques in Social Networks: A New Distribution-Free Model (Fox, Roughgarden, Seshadhri, Wei, Wein) |
13.11.2018 16:15 Mateusz Pabian |
New approximation algorithm for (1,2)-TSP (Adamaszek, Mnich, Paluch) |
06.11.2018 16:15 Szymon Łukasz |
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors (A. Bhangale) |
We give very short and simple proofs of the following statements: Given a 2-colorable 4-uniform hypergraph on n vertices, 1) It is NP-hard to color it with log^delta n colors for some delta>0. 2) It is quasi-NP-hard to color it with O({log^{1-o(1)} n}) colors. |
30.10.2018 16:15 Wiktor Daniec |
David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5) |
David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5) |
14.04.2015 Maciej Solon |
Graphs defined by forbidden patterns. |
13.01.2015 Andrzej Dorobisz. |
Treewidth. Courcelle's theorem. |
16.12.2014 Grzegorz Gutowski. |
s-t orientations of planar graphs. |
02.12.2014 Andrzej Dorobisz |
Treewidth. |
25.11.2014 18.11.2014,Patryk Mikos |
Kernelization and Linear Programming Techniques |
03.06.2014 M. Solon, P. Wójcik |
Polynomial coloring of 3-colorable graphs. |
27.05.2014 20.05.2014 13.05.2014 Adam Gągol |
Constraint Satisfaction, Packet Routing, and the Lovász Local Lemma (by Harris and Srinivasan) |
|
15.04.2014 Grzegorz Gutowski, Jakub Kozik |
Lower bounds for on-line graph colorings (cont.) |
(join work with P. Micek and X. Zhu) |
08.04.2014 01.04.2014, |
Cancelled (all participants are invited to the lecture of prof. A. Ruciński.) |
18.03.2014 Grzegorz Gutowski, Jakub Kozik |
Lower bounds for on-line graph colorings |
(join work with P. Micek and X. Zhu) |
04.03.2014 Igor Adamski |
Outer-string graphs are chi-bounded |
References:Alexandre Rok, Bartosz Walczak, Outer-string graphs are chi-bounded, preprint |
21.01.2014 Maciej Solon |
On the number of edges in families of pseudo-discs |
References:Piotr Micek, Rom Pinchasi, On the number of edges in families of pseudo-discs, preprint |
14.01.2014 Maciej Bendkowski |
List Colouring When The Chromatic Number Is Close To the Order Of The Graph |
References:B. Reed, B. Sudakov, List Colouring When The Chromatic Number Is Close To the Order Of The Graph, Combinatorica December 2004, Volume 25, Issue 1, pp 117-123 |
07.01.2014 Aneta Pawłowska |
Three Topics in Online List Coloring |
References:J. Carraher, S. Loeb, T. Mahoney, G. Puleo, M. Tsai, D.B. West,Three Topics in Online List Coloring, preprint |
17.12.2013 10.12.2013,Damian Królik |
Sum-paintability of generalized theta-graphs |
References:J. Carraher, T. Mahoney, G.J. Puleo, D.B. West , Sum-paintability of generalized theta-graphs, preprint |
26.11.2013 Wojciech Łopata |
Conflict-Free Colourings of Uniform Hypergraphs With Few Edges |
References:A.V. Kostochka, M. Kumbhat, T. Łuczak, Conflict-Free Colourings of Uniform Hypergraphs With Few Edges, Combinatorics, Probability and Computing Volume 21 Issue 4, July 2012 |
12.11.2013 Tomasz Krawczyk, Bartosz Walczak |
Coloring subtree overlap graphs with O(log lgo n) colors. |
05.11.2013 Grzegorz Guśpiel |
On the construction of 3-chromatic hypergraphs with few edges. |
References:Heidi Gebauer, On the construction of 3-chromatic hypergraphs with few edges, JCTA 120 (2013) |
- Home
- Algorithmics Research Group
- Foundations of Computer Science
- Faculty of Mathematics and Computer Science
- Contact
- Satori
- Reports on Mathematical Logic
- Forum TCS
- UsosWeb
- Informatyka na szlaku
- Photos
- People
- Demian Banakh
- Bartłomiej Bosek
- Marcin Briański
- Iwona Cieślik
- Jan Derbisz
- Andrzej Dorobisz
- Lech Duraj
- Monika Gillert
- Katarzyna Grygiel
- Grzegorz Gutowski
- Grzegorz Herman
- Jędrzej Hodor
- Pawel M. Idziak
- Marcin Kozik
- Jakub Kozik
- Jacek Krzaczkowski
- Agnieszka Łupińska
- Piotr Micek
- Piotr Mikołajczyk
- Jonathan Narboni
- Andrzej Pezarski
- Bartosz Podkanowicz
- Adam Polak
- Krzysztof Potępa
- Wojciech Szpankowski
- Maciej Ślusarek
- Jan Tułowiecki
- Krzysztof Turowski
- Bartosz Walczak
- Michał Wrona
- Marek Zaionc
- Former colleagues